Основы теории передачи информации


Итеративный код


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

Предположим, что нужно передать, к примеру, девять информационных символов m = ( m0 , m1 , ..., m8 ). Эти символы можно расположить в виде квадратной матрицы, как это показано в табл. 1.1, и добавить к каждой строке и каждому столбцу этой таблицы по проверочному символу (проверка на четность).

         Таблица 1.1

m0

m1

m2

P1 = m0 +m1 +m2

m3

m4

m5

P2 = m3 +m4 +m5

m6

m7

m8

P3 = m6  + m7

+ m8

m0 +m3 +m6

m1+ m4 +m7

m2 +m5 +m8

m0 + m0 + m1 + m1 +…. +  m8 + m8

Таким образом, по строкам и по столбцам этой таблицы будет выполняться правило четности единиц. 

Если в процессе передачи по каналу с помехами в этой таблице произойдет одна ошибка (например  в символе m4), то проверка на четность в соответствующей строке  и  столбце (в нашем примере - P2 и P5) не будет выполняться.

Иными словами,  координаты ошибки однозначно определяются  номерами столбца и строки, в которых не выполняются проверки на четность. Таким образом, этот код, используя различные

проверки на четность (по строкам и по столбцам), способен не только обнаруживать, но и исправлять ошибки (если известны координаты ошибки, то ее исправление состоит просто в замене символа на противоположный: если 0, то на 1, если 1 – то на 0 ). 

Описанный метод кодирования, называемый итеративным, оказывается полезным в случае, когда данные естественным образом формируются в виде массивов, например, на шинах ЭВМ, в памяти, имеющей табличную структуру, и т.д.  При этом размер таблицы в принципе не имеет значения (3х3 или 20х20), однако в первом случае будет исправляться одна ошибка на 3х3=9 символов, а во втором – на 20х20=400 символов.

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

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




Начало  Назад  Вперед



Книжный магазин