Бит чётности
В коде Хэмминга биты кодового слова нумеруются последовательно слева направо,
начиная с 1. Биты с номерами, равными степеням 2 (1, 2, 4, 8, 16 и т. д.), являются
контрольными. Остальные биты (3, 5, 6, 7, 9, 10 и т. д.) заполняются m битами данных.
Каждый контрольный бит обеспечивает сумму по модулю 2 или четность некоторой
группы бит, включая себя самого. Один бит может входить в несколько вычислений
контрольных бит. Чтобы определить, в какие группы контрольных сумм будет входить
бит данных в k-й позиции, следует разложить k по степеням числа 2. Например, 11 = 8 +
2 + 1, а 29 = 16 + 8 + 4 + 1. Каждый бит проверяется только теми контрольными битами,
номера которых входят в этот ряд разложения (например, 11-й бит проверяется битами
1, 2 и 8). В нашем примере контрольные биты вычисляются для проверки на четность в
сообщении, представляющем букву «A» в кодах ASCII.
5.
В последовательных коммуникациях чётность обычно
контролируется оборудованием интерфейса (например
UART). Признак ошибки становится доступен процессору
через статусный регистр оборудования. Восстановление
ошибок обычно производится повторной передачей
данных, подробности которого обрабатываются
программным обеспечением (например, функциями
ввода-вывода операционной системы)
6.
Код Рида-Соломона
7.
Коды Рида-Соломона основываются на том, что каждый многочлен n-й степени
уникальным образом определяется n + 1 точкой. Например, если линия задается
формулой ax + b, то восстановить ее можно по двум точкам. Коды Рида—Соломона
определяются как многочлены на конечных полях. Для m-битовых символов длина
кодового слова составляет 2m – 1 символов. Очень часто выбирают значение m = 8, то
есть одному символу соответствует один байт. Тогда длина кодового слова — 255 байт.
Широко используется код (255,233), он добавляет 32 дополнительных символа к 233
символам данных. Декодирование с исправлением ошибок выполняется при помощи
алгоритма Берлекэмпа-Мэсси, который осуществляет подгонку для кодов средней
длины. При добавлении 2t избыточных символов код Рида-Соломона способен
исправить до t ошибок в любом из переданных символов. Это означает, например, что
код (255,233) с 32 избыточными символами исправляет до 16 ошибок. Так как символы
могут быть последовательными, а размер их обычно составляет 8 бит, то возможно
исправление последовательных ошибок в 128 битах. Коды Рида-Соломона часто
используют в сочетании с другими кодами, например сверточными. Сверточные коды
эффективно обрабатывают изолированные однобитные ошибки, но с
последовательностью ошибок они не справятся, особенно если ошибок в полученном
потоке бит слишком много. Добавив внутрь сверточного кода код Рида-Соломона, вы
сможете очистить поток бит от последовательностей ошибок.
8.
9.
10.
Литература.
Питерсон У., Уэлдон Э. Коды, исправляющие ошибки.
Блейхут Р. Теория и практика кодов, контролирующих ошибки
Берлекэмп Э. Алгебраическая теория кодирования
Егоров С.И. Коррекция ошибок в информационных каналах периферийных устройств
Сагалович Ю. Л. Введение в алгебраические коды: Учебное пособие.
Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования.
М. Вернер. Основы кодирования.
Генри С. Уоррен, мл. Глава 5. Подсчет битов .
Задание 5. Выполнение, анализ и поиск алгоритмов
За правильное выполненное задание получишь 1 балл. На решение отводится примерно 4 минуты.
Для выполнения задания 5 по информатике необходимо знать:
- Сумма двух цифр в десятичной системе счисления находится в диапазоне от 0 до 18 (9+9)
- В некоторых задачах нужно иметь представление о системах счисления (могут использоваться цифры восьмеричной и шестнадцатеричной систем счисления)
- Бит чётности – это дополнительный контрольный бит, который добавляется к двоичному коду так, чтобы количество единиц в полученном двоичном коде стало чётным; если в исходном коде уже было чётное количество единиц, дописывается 0, если нечётное – дописывается 1.
Задачи для тренировки
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится двоичная запись числа N.
- К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает число 83 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Что такое бит четности в информатике
Недавно Маша и Катя узнали, что в мире существуют злые хакеры, которые могут запросто вскрыть чужую переписку. Поэтому решили они пересылать только зашифрованные сообщения. Для этой цели подруги стали использовать перестановочный код, где каждая буква заменяется другой. Например:
Закодированное сообщение: HPC PJVYMIY
Декодированное сообщение: ACM CONTEST
В этом примере выполнены следующие замены:
H=A, P=C, C=M, J=O, V=N, Y=T, M=E и I=S.
Чтобы не заниматься кодированием и декодированием вручную, подруги просят Вас написать программу. Помогите девочкам!
Входные данные
В первой строке входных данных записано закодированное сообщение содержащее не более 100 символов. Вторая строка — 26 латинских букв верхнего регистра, представляющих собой код для соответствующего символа алфавита: первый символ дает код для A, второй для B и так далее. Используются только буквы верхнего регистра. В закодированном сообщении могут появиться пробелы, которые должны быть сохранены в выходной строке.
Выходные данные
Выведите одну строку, в которой содержится расшифрованное сообщение.
Входные данные
HPC PJVYMIY BLMRGJIASOPZEFDCKWYHUNXQTV
Выходные данные
ACM CONTEST
Входные данные
FDY GAI BG UKMY KIMHOTSQYRLCUZPAGWJNBVDXEF
Выходные данные
THE SKY IS BLUE
Источники: [ Командные олимпиады, Барнаульские командные турниры, 2009, Задача B ]
ограничение по времени на тест
ограничение по памяти на тест
256 megabytes
Витя — очень любит что-нибудь придумывать. Однажды он придумал сделать для мамы робота, который будет кормить рыбок в аквариуме. Рыбки — существа нежные, кормить их надо строго по заданной программе, поэтому Витя особое внимание хочет уделить надежности робота. Витя учел, что роботу придется открывать аквариум, следовательно, есть опасность попадания воды на микросхемы. Но хитрый Витя придумал сложную систему защиты от сбоев, основанную на контроле четности двоичного представления выполняющихся команд робота. Причем для команд разных видов Витя решил использовать разный принцип контроля четности — для одних команд будет работать система контроля четности, а для других — система контроля нечетности.
Витя знает, что битовая последовательность имеет нечетный бит четности, если число единиц в последовательности нечетное. И наоборот, последовательность имеет четный бит четности, если число единиц — четное. Считается, что число нуль будет четным числом, поэтому последовательность без единиц имеет четный бит четности. Витя даже хочет подсказать Вам, что количество нулей не влияет на бит четности последовательности.
Входные данные
Во входном файле содержится единственная строка. Эта строка содержит от 1 до 31 бит, а заканчивается буквой ‘e’ или ‘o’.
Выходные данные
Выведите соответствующую последовательность битов, которая заканчивается битом четности:
четным, если строка заканчивалась символом ‘e’,
нечетным, если строка заканчивалась символом ‘o’.
Объясните что такое бит чётности в портах, нужно понятное объяснение как вы это понимаете. (чет, нечет, нет, маркер, пробел)
Смотрите скриншот, если не поняли.
Голосование за лучший ответ
Смотри, порт работает с определенной скоростью. Например он каждую секунду проверяет напряжение на порту. Есть напряжение — передается единица, нет напряжения — 0. Мы хотим передать пакет данных через порт. Наш пакет состоит из набора бит. Первый бит (так называемый СТАРТОВЫЙ) передает логический ноль — выключает напряжение на порту, это дает понять системе что началась передача пакета, и следующие 8 секунд изменение напряжения будет соответствовать нулям и единицам данных. Далее передается информация — логические нули и единицы. То есть по протоколу положено что в пакете 8 бит, вот и система после стартового бита принимает 8 бит (по одному за секунду, например 11010110). Далее по протоколу положено получить бит четности. Он является единицей если количество единиц в данных четное, или ноль если не четное. В нашем случае (11010110) количество единиц в пакете нечетное, потому бит четности будет равен нулю. И теперь, если вдруг произошел косяк в сети, и информация дошла не верно (например вместо 11010110 пришло 11011110) то бит четности будет ошибочен, и система поймет что данные дошли не правильные. Все цифры и скорости естественно от балды я написал, все они определяются протоколами.
Vray_powerУченик (103) 9 лет назад
Одним словом, что мне лучше поставить?
Fabricant Знаток (304) Все зависит от того что подключать требуется. Я вот недавно настраивал ком порт под систему опроса для электрических счетчиков, так в инструкции к софту были прописаны все параметры требуемые для работы с устройством.
Похожие вопросы