2.4. Принципы помехоустойчивого кодирования

В реальных каналах передачи и хранения двоично-кодированной информации возможно ее искажение – вместо символа «1», поступившего на вход канала, на его выходе может быть получен символ «0» или наоборот.

Общепринятым критерием оценки достоверности (или безошибочности) передачи и хранения информации в дискретных каналах является нормированная на знак или на символ допустимая вероятность ошибки. Так, допустимая вероятность ошибки для телеграфной связи может составлять 10^–3 на знак, а при передаче или хранении двоично-кодированных данных – не более 10^–6 на символ. Допустимую вероятность ошибки следует интерпретировать следующим образом: например, если ее значение равно 10^–3 на знак, то это значит, что на каждую тысячу знаков в среднем приходится одна ошибка; если же значение допустимой вероятности на символ равна 10^–6 , то это означает, что в среднем одна ошибка приходится на каждый миллион символов.

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

Поясним сказанное. Пусть М – это число (или множество) сообщений, подлежащих передаче или хранению. Каждому из сообщений поставим в соответствие m – разрядное двоичное слово А=а_m a_m–1… a₁, причем где – ближайшее целое большее или равное V. Полученное множество слов, именуемых информационными, образует простой код, в котором все m разрядов (информационные разряды) используются для кодирования собственно сообщения. Введение избыточности предполагает дополнение по определенным правилам (алгоритмам) m – разрядных информационных слов k дополнительными или избыточными разрядами. Эти разряды, именуемые проверочными или контрольными, используют для того, чтобы придать каждой кодовой комбинации, поступающей на вход канала, некоторый характерный признак, контролируя наличие которого на выходе из канала, можно судить о ее безошибочности, а в отдельных случаях и исправлять возникшие ошибки.

Таким образом, введение информационной избыточности предполагает наращивание разрядности информационных слов от значения m до некоторого значения n=m+k. При этом из n двоичных символов можно образовать различных кодовых комбинаций, из которых только являются разрешенными (рабочими), т.е. обладающими определенным искусственно приданным им признаком, и именно они используются для передачи или хранения сообщений. Остальные N–M кодовые комбинации являются запрещенными и не обладают признаком, характерным для разрешенных.

Полученные подобным образом n – разрядные разрешенные кодовые комбинации именуют кодовыми словами, а множество М кодовых слов образует помехоустойчивый или избыточный код.

Процедура перехода от m – разрядных информационных слов А к соответствующим n – разрядным кодовым словам А_к именуется кодированием и осуществляется она по определенным правилам или алгоритмам , индиви-дуальным для каждого из известных помехоустойчивых кодов.

Кодирование может быть реализовано как с помощью специализированных устройств – кодирующих устройств (или кодеров), так и программными методами на ЭВМ (рис. 2.3).

Рис. 2.3. Кодирование для последовательного а) и параллельного б) каналов

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

Для возможности коррекции ошибок необходимо использовать некоторый критерий, позволяющий по полученной из канала искаженной кодовой комбинации осуществить выбор из множества разрешенных комбинаций той, которая предположительно была подана на его вход. В дискретных каналах, в которых наиболее вероятны независимые ошибки, в качестве такого критерия выбора применяют принцип максимального правдоподобия, в основу которого положено предложение, что в канале вероятность ошибки большей кратности меньше вероятности ошибки меньшей кратности (см. раздел 2.2). Если такое предложение справедливо, оправдано отождествлять с передаваемой комбинацией ту из разрешенных, которая отличается от полученной искаженной в наименьшем числе разрядов.

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

Рис. 2.4. Декодирование в режиме обнаружения а) и коррекции ошибок б)

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

Таблица 2.6

Сообще- ния	Информационные слова А = а2 а1	Код с контролем нечетности Ак= а2 а1
S1 S2 S3 S4	А1= 0 0 А2= 0 1 А3= 1 0 А4= 1 1	Ак1=0 0 1 Ак2=0 1 0 Ак3=1 0 0 Ак4=1 1 1

Например, при передаче слова А₂=01 и искажении в канале первого разряда на выходе из канала получим слово А₄=11, также разрешенное.

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

, i=1,2,3,4.

Разрешенные кодовые комбинации полученного таким образом кода, именуемого кодом с контролем нечетности, приведены в табл. 2.6. Остальные трехразрядные кодовые комбинации (их как и разрешенных – четыре) являются запрещенными. При передаче по каналу кодового слова, например А_к2=010 и искажении в канале одного из разрядов, допустим, первого, на выходе из канала получим . Поскольку не входит в перечень разрешенных делается заключение об его ошибочности. Следовательно, код с контролем нечетности (как и код с контролем четности, рассмотренный в Примере 2.4) позволяет обнаруживать в кодовых словах любые одинарные ошибки, а также ошибки произвольной нечетной кратности. В то же время код с контролем нечетности не позволяет выявлять в кодовых словах ошибки четной кратности. Так, если в передаваемом кодовом слове, например – А_к2=010, исказятся два разряда, допустим – первый и второй, то на выходе из канала получим кодовую комбинацию 100, являющуюся разрешенной (соответствует А_к3) и, следовательно, ошибка не выявляется. Кроме того, код с контролем нечетности (как и код с контролем четности) не позволяет локализовать ошибку и, следовательно, исправить ее. Действительно, искаженная кодовая комбинация 011 на выходе из канала может быть получена при передаче кодовых слов: А_к1=001 и искажении второго разряда, А_к2=010 и искажении третьего разряда, А_к4=111 и искажении первого разряда.

Пример 2.6. Преобразуем двухразрядные информационные слова в пятиразрядные кодовые слова избыточного кода в соответствии со следующим алгоритмом.

1.Образуем из символов информационного слова А=а₂а₁ три группы, включающие символы: 1 группа – а₂ и а₁, 2 группа – а₁ и 3 группа – а₂;

2.Добавим к каждой из групп по одному проверочному символу, значение которого выберем таким образом, чтобы группа с учетом и проверочного символа стала четной, т.е. , , .

Таблица 2.7

Информацион-ные слова А = а2 а1	Кодовые Слова Ак= а2 а1 α3 α2 α1
А1= 0 0 А2= 0 1 А3= 1 0 А4= 1 1	Ак1=0 0 0 0 0 Ак2=0 1 0 1 1 Ак3=1 0 1 0 1 Ак4=1 1 1 1 0

Информационные и соответст-вующие им кодовые слова сведены в табл. 2.7.

Остальные, не приведенные в таблице пятиразрядные кодовые комбинации, общее число которых равно 2⁵-4=28, являются запрещенными.

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

Допустим, что в передаваемом по каналу кодовом слове А_к3=10101 исказился второй разряд и, следовательно, на выходе из канала получена кодовая комбинация , не входящая в перечень кодовых слов и, следовательно, делается заключение об ее ошибочности. Учитывая далее то, что полученная из канала искаженная кодовая комбинация 11101 отличается от кодового слова А_к3=10101 всего одним символом (вторым), а от остальных кодовых слов двумя или тремя символами, делается заключение, что передавалось кодовое слово А_к3 и соответствующее ему информационное слово А₃=10.

Следовательно, код позволяет не только установить ошибочность кодовой комбинации, полученной из канала, но и восстановить кодовое слово, поступившее на его вход, т.е. исправить (скорректировать) ошибку.

Проанализируем поведение рассматриваемого кода в случае, когда в передаваемом кодовом слове, например слове А_к3=10101, в канале исказится два разряда, допустим второй и пятый. При этом на выходе из канала будет получена кодовая комбинация 11100, не принадлежащая подмножеству разрешенных (приведенных в табл. 2.7) и, следовательно, декодер установит факт ее ошибочности. Для исправления ошибок декодер отыскивает в перечне разрешенных кодовых комбинаций ту, которая отличается от полученной искаженной наименьшим числом разрядов (так как в основу его работы положен принцип максимального правдоподобия). Поскольку декодеру не известно сколько фактически разрядов в полученной кодовой комбинации искажено за передаваемое кодовое слово он принимает кодовое слово А_к4=11110, как отличающиеся от полученной из канала искаженной кодовой комбинации всего одним разрядом – четвертым. В результате будет сделано ложное заключение, что передавалось кодовое слово А_к4 и ошибка пришлась на четвертый разряд этого слова тогда, как фактически передавалось слово А_к3 и оно искажено двумя ошибками. Следовательно, код способен обнаруживать одинарные и двойные ошибки, исправлять одинарные ошибки, а исправлять двойные ему уже не под силу.

Из рассмотренных Примеров 2.5 и 2.6 можно сделать следующий вывод. Некоторые из помехоустойчивых кодов позволяют только обнаруживать ошибки определенной кратности, другие – способны не только обнаруживать, но и исправлять ошибки определенной кратности. Естественно возникают вопросы: От чего зависят обнаруживающие и корректирующие способности кода? Как построить код с требуемыми возможностями? Ответы на эти вопросы будут даны в последующих разделах главы.