Главная > Разное > Теория кодирования и теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3.2. Прямоугольные коды

Первыми и наиболее простыми кодами с исправлением ошибок являются коды с утроением, в которых каждое передаваемое сообщение повторяется три раза, а на приемном конце производится голосование по большинству. Ясно, что такая система

исправляет любые одиночные ошибки. Однако не менее ясно, что такая система кодирования очень неэффективна. Три параллельных ЭВМ вместе с устройством сравнения и прерывания при необходимости оказываются слишком дорогими. Поэтому нужно искать лучшие методы кодирования информации, позволяющие исправлять одну ошибку.

Следующими по простоте кодами с исправлением ошибок являются прямоугольные коды, в которых сообщение представляется в прямоугольниках размером (рис. 3.2.1), хотя фактически сообщение не обязано иметь такой вид. Затем каждой строке, состоящей из символов, добавляется проверка на четность, так что длина строки становится равной символам. Аналогично, к каждому столбцу добавляется по одному проверочному символу. При этом несущественно, заполняется или нет правый нижний угол. Проверочный символ выбирается так, чтобы общая сумма была четной, тогда четность последней строки равна четности крайнего правого столбца. Таким образом, первоначальный прямоугольник из двоичных символов превращается в массив из двоичных символов. Поэтому избыточность равна При заданном избыточность тем меньше, чем ближе прямоугольник к квадрату. Для квадратных кодов размера имеется информационных символов и проверочных символов вдоль сторон.

Прямоугольный код использовался, например, в запоминающих устройствах на электронно-лучевых трубках в ЭВМ NORC. Прямоугольные коды часто применяются в на магнитных лентах [3, 15]. Продольные проверки на четность проводятся вдоль строк и в конце блока добавляется еще одна строка для формирования вертикальной проверки на четность. К сожалению, проектировщики редко разрешают пользователю извлекать информацию о проведенных проверках на четность и исправлять отдельные ошибки с помощью подходящих программ.

Задачи

3.2.1. Рассмотрите все возможные прямоугольные коды с 24 информационными символами.

3.2.2. Обсудите использование углового проверочного символа. Докажите, что при проверках на четность он является проверочным символом как для строки, так и для столбца. Рассмотрите применение в этой связи проверок на нечетность.

Рис. 3.2.1. Прямоугольные коды: О — позиции сообщений; X — проверочные позиции

<< Предыдущий параграф Следующий параграф >>
Оглавление