Примеры простейших кодов

Код с проверкой на четность. Самым простым линейным блочным кодом является (п, п- 1)-код, построенный с помощью одной общей проверки на четность. Например, кодовое слово (4, 3)-кода можно записать в виде вектора-столбца:

где т, — символы исходной информационной последовательности, принимающие значения 0 и 1, а суммирование производится по модулю 2 и обозначается символом ©.

Основная идея проверки на четность состоит в следующем. Пусть информационная последовательность источника имеет вид т = (1 0 1).

Тогда соответствующая ей кодовая последовательность будет выглядеть так: , где проверочный символ и_л формируется путем суммирования символов информационной последовательности т:

Если число единиц в последовательности т четно, то результатом суммирования будет 0, если нечетно — 1, т. е. проверочный символ дополняет кодовую последовательность таким образом, чтобы количество единиц в ней было четным.

При передаче по каналам связи в принятой последовательности возможно появление ошибок, т. е. символы принятой последовательности могут отличаться от соответствующих символов переданной кодовой последовательности (нуль переходит в единицу, а 1 — в 0). Если при передаче рассматриваемого (4, 3)-кода произошла одна ошибка, причем неважно, в какой его позиции, то общее число единиц в принятой последовательности уже не будет четным. Таким образом, признаком отсутствия ошибки в принятой последовательности может служить четность числа единиц. Поэтому такие коды и называются кодами с проверкой на четность. Правда, если в принятой последовательности произошло две ошибки, то общее число единиц в ней снова станет четным и ошибка обнаружена не будет. Однако вероятность двойной ошибки значительно меньше вероятности одиночной, поэтому наиболее вероятные одиночные ошибки таким кодом обнаруживаться все же будут.

Отметим следующий момент. Если посимвольно сложить два кодовых слова, принадлежащих рассматриваемому (4, 3)-коду:

то получим.

т.е. проверочный символ в новом слове с определяется по тому же правилу, что и в слагаемых. Поэтому с также является кодовым словом данного кода.

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

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

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

Предположим, что нужно передать, к примеру, девять информационных символов т = (Ш], т₂, …, т₉). Эти символы можно расположить в виде квадратной матрицы, как это показано в табл. 4.1, и добавить к каждой строке и каждому столбцу этой таблицы по проверочному символу (проверка на четность).

Таблица 4.1

Формирование проверочных символов итеративного кода.

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

Если в процессе передачи по каналу с помехами в этой таблице произойдет одна ошибка (например, в символе т₄), то проверка на четность в соответствующей строке и столбце (в данном случае — в первом столбце и второй строке) не будет выполняться. Иными словами, координаты ошибки однозначно определяются номерами столбца и строки, в которых не выполняются проверки на четность. Таким образом, этот код, используя различные проверки на четность (по строкам и по столбцам), способен не только обнаруживать, но и исправлять ошибки (если известны координаты ошибки, то ее исправление состоит просто в инверсии, т. е. замене символа на противоположный: если 0, то на 1, если 1 — то на 0).

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

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

«Облачный» код. Разместим четырехразрядное слово т = (т₁, т₂, т₃, т₄), которое требуется закодировать, в областях пересечения трех кругов («облаков»), а в свободных местах «облаков» поместим три дополнительных символа так, чтобы в каждом «облаке» сумма битов была четной, т. е. нулевой (рис. 4.2).

Рис. 4.2. Иллюстрация облачного кода.

При искажении любого из разрядов исходной комбинации т четность нарушится в двух или трех «облаках». По тому, в каких именно «облаках» обнаружена нечетность, можно определить место ошибки, а следовательно, исправить ее. Например, если после передачи семиразрядного слова будет обнаружены нечетные суммы в левом и правом верхних «облаках», это свидетельствует об ошибке в разряде т_а. Если же нечетные суммы будут во всех трех «облаках», это говорит об ошибке в разряде т₂. Нечетная сумма только в одном из «облаков» означает ошибку в дополнительном разряде, которую можно не исправлять. Отметим, что этот код можно определить как (7, 4)-код и он относится к классу оптимальных, т. е. для заданного количества информационных разрядов имеет минимально возможное число проверочных битов.