Задание 5. Выполнение, анализ и поиск алгоритмов
За правильное выполненное задание получишь 1 балл. На решение отводится примерно 4 минуты.
Для выполнения задания 5 по информатике необходимо знать:
- Сумма двух цифр в десятичной системе счисления находится в диапазоне от 0 до 18 (9+9)
- В некоторых задачах нужно иметь представление о системах счисления (могут использоваться цифры восьмеричной и шестнадцатеричной систем счисления)
- Бит чётности – это дополнительный контрольный бит, который добавляется к двоичному коду так, чтобы количество единиц в полученном двоичном коде стало чётным; если в исходном коде уже было чётное количество единиц, дописывается 0, если нечётное – дописывается 1.
Задачи для тренировки
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
- Строится двоичная запись числа N.
- К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает число 83 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Бит чётности
В коде Хэмминга биты кодового слова нумеруются последовательно слева направо,
начиная с 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. Подсчет битов .
Объясните что такое бит чётности в портах, нужно понятное объяснение как вы это понимаете. (чет, нечет, нет, маркер, пробел)
Смотрите скриншот, если не поняли.
Голосование за лучший ответ
Смотри, порт работает с определенной скоростью. Например он каждую секунду проверяет напряжение на порту. Есть напряжение — передается единица, нет напряжения — 0. Мы хотим передать пакет данных через порт. Наш пакет состоит из набора бит. Первый бит (так называемый СТАРТОВЫЙ) передает логический ноль — выключает напряжение на порту, это дает понять системе что началась передача пакета, и следующие 8 секунд изменение напряжения будет соответствовать нулям и единицам данных. Далее передается информация — логические нули и единицы. То есть по протоколу положено что в пакете 8 бит, вот и система после стартового бита принимает 8 бит (по одному за секунду, например 11010110). Далее по протоколу положено получить бит четности. Он является единицей если количество единиц в данных четное, или ноль если не четное. В нашем случае (11010110) количество единиц в пакете нечетное, потому бит четности будет равен нулю. И теперь, если вдруг произошел косяк в сети, и информация дошла не верно (например вместо 11010110 пришло 11011110) то бит четности будет ошибочен, и система поймет что данные дошли не правильные. Все цифры и скорости естественно от балды я написал, все они определяются протоколами.
Vray_powerУченик (103) 8 лет назад
Одним словом, что мне лучше поставить?
Fabricant Знаток (304) Все зависит от того что подключать требуется. Я вот недавно настраивал ком порт под систему опроса для электрических счетчиков, так в инструкции к софту были прописаны все параметры требуемые для работы с устройством.
Похожие вопросы
Бит чётности
В вычислительной технике и сетях передачи данных би́том чётности называют контрольный бит, принимающий значения ‘0’ или ‘1’ и служащий для проверки общей чётности двоичного числа (чётности количества единичных битов в числе).
В задачах ЕГЭ имеет следующее описание:
Складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001