9.3. Декодирование циклических AN-кодов

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

9.3.1. Вычеты по модулю А и конфигурации ошибок

Тогда как при построении и вычислении минимального расстояния циклических AN-кодов важную роль выполняют вычеты по модулю В, при исправлении ошибок более важными оказываются вычеты по модулю А. Установим сначала связь между ошибками и вычетами по модулю А, а также укажем некоторые свойства ошибок.

Ошибка всегда может быть задана с помощью двоичного представления целого числа Е:

(здесь - длина кода). Ошибка получается сдвигом двоичного представления ошибки на разрядов влево и имеет ту

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

Если в процессе передачи в арифметическом устройстве возникает ошибка, в результате которой вместо кодового слова принимается другое слово, то последнее всегда можно представить в виде

Взяв остаток от деления числа, соответствующего этому слову, на А, получим

Этот остаток зависит только от ошибки как указывалось в разд. 8.7, часто называется синдромом. Если синдром равен нулю, то ошибка не обнаруживается (это имеет место, если ошибки не возникают или если возникают необнаруживаемые ошибки). Если синдром отличен от нуля, то это означает, что произошла ошибка.

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

Следующая лемма устанавливает взаимно однозначное соответствие между ошибками и вычетами по модулю А.

Лемма 9.4. Если является исправляемой конфигурацией ошибок, т. е. если

то ни при каком вычет

не совпадает с Кроме того, если то

Доказательство. Поскольку то

Если

Так как минимальное расстояние кода равно то для всех Следовательно,

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

Так как то и А не являются взаимно простыми. Пусть Тогда

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

Пример 9.3. Циклический AN-код длины содержащий кодовых слов является кодом, исправляющим ошибки веса 2. Рассмотрим следующую исправляемую конфигурацию ошибок:

Эта конфигурация является двоичным представлением числа 513. Легко проверить, что Ошибка совпадает с приведенной выше конфигурацией и

Лемма 9.5. Если исправляемая конфигурация ошибок удовлетворяет условию то вычет исправляемой ошибкой не является.

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

Следовательно,

Однако так как то

Таким образом, для веса мы получили следующую верхнюю границу:

Эта граница показывает, что не является исправляемой ошибкой.

Пример 9.4. В табл. 9.16 приведены результаты вычисления вычетов для кода из примера 9.3 и конфигурации ошибок Эта таблица служит хорошим примером к лемме 9.5.

Таблица 9.16 (см. скан) Циклические сдвиги конфигурации ошибок и вес соответствующих вычетов

9.3.2. Метод декодирования, основанный на циклических сдвигах вычетов

В этом разделе описывается алгоритм декодирования, использующий циклический сдвиг вычетов. Сначала заметим, что если то

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

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

Пример 9.5. Вновь рассмотрим циклический AN-код с параметрами использованный ранее в примерах 9.3 и 9.4. Этот код исправляет ошибки веса 2. Предположим, что вычет по модулю принятого кодового слова равен 7761. Его вес равен 5 и превышает 2. Поэтому, согласно описанному алгоритму декодирования, будем сдвигать этот вычет влево, вычисляя после каждого сдвига вычет по модулю А и его вес.

Таблица 9.17 (см. скан) при

Результаты этих вычислений приведены в табл. 9.17, где вычет по модулю А принятого кодового слова, вычет по модулю А после сдвигов. Так как лежит в области корректирующей способности кода, то 5-й и последующие сдвиги проводить не нужно. Конфигурация ошибок в данном случае имеет вид

Осуществляя четыре сдвига в обратном направлении, находим ошибку

Вычитая эту ошибку из принятого кодового слова, получаем исходное кодовое слово.

Если бы в действительности возникла ошибка 7761, имеющая двоичное представление

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

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

Например, в табл. 9.18 приведены вычеты для кода из примера 9.5 и ошибок

Таблица 9.18 (см. скан) Вычеты

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

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

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

На фиг. 9.3 приведена блок-схема алгоритма декодирования, детально описанного выше.

9.3.3. Метод декодирования, основанный на переборе

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

кода, то это кодовое слово является искомым кодовым словом.

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

Фиг. 9.3. (см. скан) Алгоритм декодирования, основанный на циклических сдвигах вычетов.

Этот метод применим не только для циклических AN-кодов, но и для произвольных и позволяет исправлять все ошибки вес которых не превосходит Однако в случае циклических -кодов

последовательное построение кодовых слов может быть реализовано сравнительно просто.

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

Лемма 9.6. Пусть два различных кодовых слова Если принято слово

и d - минимальное расстояние кода, то неравенства

одновременно выполняться не могут. Кроме того, если выполняется первое из этих неравенств, то

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

Однако так как код имеет минимальное расстояние то и мы получили противоречие. Следовательно, если то приведенные в формулировке леммы два неравенства одновременно выполняться не могут. Справедливость равенства при условии, что доказывается аналогично.

На фиг. 9.4 приведена блок-схема описанного выше алгоритма декодирования, в котором, однако, предусмотрено обнаружение ошибок путем вычисления вычета по модулю А для принятого слова.

Фиг. 9.4. (см. скан) Алгоритм декодирования, основанный на переборе.