Итеративный код
Еще одна простая схема кодирования, которая также часто используется, может быть построена следующим образом.
Предположим, что нужно передать, к примеру, девять информационных символов 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 символов.
Обратим внимание еще на один момент. Если в простом коде с проверкой на четность для обнаружения ошибки приходится добавлять к информационной последовательности всего один символ, то для того, чтобы код стал исправлять однократную ошибку, понадобилось к девяти информационным символам добавить еще семь проверочных.
Таким образом, избыточность этого кода оказалась очень большой, а исправляющая способность – сравнительно низкой. Поэтому усилия специалистов в области помехоустойчивого кодирования всегда были направлены на поиск таких кодов и методов кодирования, которые при минимальной избыточности обеспечивали бы максимальную исправляющую способность.
