5.4. Декодирование с использованием списков на основе кластеров

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

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

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

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

Рис. 5.4. Структурная схема декодера с исчправлением стираний

Декодер с исправлением стираний содержит блок приема 1, один выход которого через анализатор сигналов 2 подключен к накопителю 3, а другой подключен к входу накопителя кодовой комбинации 4.

Выход этого блока подключен к первому входу блока исправления стираний 11, вход которого подключен к выходу блока сравнения 10, при этом первый вход коммутатора проверок 5 подключен к выходу накопителя 3, а второй вход подключен к выходу накопителя кодовой комбинации 4.

Выход блока 5 подключен к одному из входов блока определения кластера 6 и к входу блока прямых координат 8, один выход которого через блок инвариантных координат 9 подключен к третьему входу блока сравнения 10, второй вход которого подключен к другому выходу блока прямых координат 8.

При этом первый выход блока определения кластера 6 подключен к входу блока коррекции кластера 7, выход которого подключен к другому входу блока определения кластера 6, второй выход которого подключен к первому входу блока сравнения 10.

Работа устройства рассматривается на примере () систематического  блокового кода.  Пусть порождающий полином кода  и , , . В метрике Хэмминга данный код способен исправить две ошибки или восстановить четыре стирания.

Блок приема 1 регистрирует поступающие сигналы и передает их текущие значения в двоичной форме в накопитель кодовой комбинации 5. Например, с  передатчика была отправлена кодовая комбинация кода:

1 0 1 0 0 1 0 1 0 1 0 0 0 0 1.

На приеме в блоке 1 эта комбинация выделяется из общего потока данных (показано  прямыми  обратными скобками) и с возможными ошибками фиксируется в блоке 4. Ошибки выделены жирным курсивом.

                             … 0 1] 1 0 0 0 1 1 1 1 1 1 0 0 0 0 1 [ 0 0… .

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

.

Или в иной форме:

здесь знак  означает сложение по модулю два.

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

В потоке стираний не стертым в первичной последовательности информационных символов присваивается значение ноль, а стертым позициям символов присваивается значение единица.

Пусть конфигурация стираний для  принятого кодового вектора имеет вид:

… 0 0 ] 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 [ 0 0 … ,

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

Для определения оценки надежности символа назначаются два скользящих окна размерами  и  битов каждое, при этом . Принцип назначения оценок описан в разделе 3.5 и соответствует аналитическому выражению (3.12).

Выход анализатора сигналов 2 подключен к входу накопителя 3, который накапливает оценки надежности  для каждого символа кодовой комбинации. После завершения обработки символов  очередной кодовой комбинации оценки   из блока 3 одновременно с комбинацией из блока 4 считываются в коммутатор проверок 5.  Например, при    для анализируемой  кодовой комбинации получаем:

• кортеж стираний из блока 1 …0 0 ] 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 [ 0 0… ;
• оценки в накопителе  3              … ] 7 6 4 4 5 6 4 6 4 7 7 8 8 8 8 [ … ;
• символы  в накопителе  4          … ] 1 0 0 0 1 1 1 1 1 1 0 0 0 0 1 [ … .

Коммутатор проверок 5 запрограммирован на деление -разрядной комбинации (в примере 15-разрядной комбинации) на участки. Старшие разряды комбинации находятся справа. Первый участок, состоящий из первых  старших разрядов предназначен для определения кластера (списка комбинаций, принадлежащих определенной группе). Всего может быть образовано кластеров (). Второй участок, представляющий половину разрядов при четном определяет координату  двумерного Евклидова пространства.  В случае нечетного значения  координате  присваивается лишний разряд. Оставшиеся разряды кодовой комбинации определяю третий участок и собственно координату .

В блоке 5 для рассматриваемого примера при получаем:

•   комбинация оценок      … ] 7 6 4 4 5      6 4 6 4 7      7 8 8 8 8  [ … ;
•   комбинация символов  … ] 1 0 0 0 1      1 1 1 1 1      0 0 0 0 1  [ … .

Все три группы символов коммутатор проверок 5 направляет в блок определения кластера 6, в блок прямых координат 8 и в блок инвариантных координат 9.

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

Блок коррекции кластера 7 объединяет данные об оценках надежности каждого символа кодовой комбинации и их информационной значимости. При этом оценка надежности получает знак  «плюс», если  в накопителе кодовой комбинации 4 ей соответствовала единица и, соответственно, «минус», если в блоке 4 был ноль.

Например, для приведенных выше кодовой комбинации и конфигурации стираний  получаем:

• символы  в накопителе 4…   ]   1 0  0  0   1   1   1    1   1   1   0  0  0   0   1 [ … ,
• состояние  блока 7              ...]+7-6 -4 -4 +5 +6 +4 +6 +4 +7 -7 -8 -8 -8 +8 [  ... .

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

Суммарные оценки в блоке 7 корректируются за несколько итераций по принципу подсчета апостериорных вероятностей (принцип Байеса). При этом на первом шаге апостериорная оценка принимается равной нолю. В корректируемой последовательности (информационные биты) выбираются два самых ненадежных символа, а остальные сворачиваются. Исходная корректируемая оценка  дополняется новой оценкой , получаемой в ходе работы блока 7. Если в результате работы блока 7 получены оценки вида, то корректировка осуществляется верно. В любом другом случает у корректируемых символов требуется замена знака. Коррекция осуществляется  по формуле:

        +

Здесь функция   возвращает знак своего аргумента;

 – оценка надежности символа, участвующего в формировании проверочного бита;

 – оценка надежности проверочного символа;

n – число сворачиваемых единиц среди информационных разрядов.

Например, в полученной для последовательности, определяющей номера кластера имеем:  +7  –6 –4 –4 +5, следовательно последние три символа требуют корректировки.  Блок 7 выбирает наиболее ненадежные символы –4 и –4, для коррекции которых подходит проверочное соотношение . Заметно, что проверочное соотношение не выполняется. Блок 7 инвертирует (меняет знак)  у символа в разряде с меньшим нижним индексом. Получаем:   +7  –6 +4 –4 +5.  Тогда   . Отсюда на первом шаге итерации получаем:

   – новое значение апостериорной оценки для символа  ;

   – новое значение для другого  символа  .

Второй шаг итерации:

 – значение коррекции для символа , при этом ;

 – значение коррекции для символа , условие   выполнено. Проверочное соотношение в результате коррекции принимает вид:  +7  –6 +12 –12 +5. Блок 7 приступает к корректировке символа . Для этого выбирается проверочное  соотношение  для , которое не выполняется. Меняется знак у символа с наименьшим индексом достоверности, при этом .

 – новое значение апостериорной оценки для символа  ;

 – новое значение для символа  .

Второй шаг итерации:

 – значение коррекции для символа , при этом ;

 – значение коррекции для символа , при этом  .

Проверочное соотношение для определения кластера  принимает окончательный вид:     +7  –6 +12 –20 –12, следовательно, в блоке 6 из  возможных кластеров фиксируется кластер с номером 1 0 1 0 02 = 2010. Эта информация используется блоком сравнения 10.

Блок прямых координат 8, работая параллельно с блоками 6 и 7, определяет значения координат  и . На основании индексов достоверности символом блок определяет и в случае необходимости корректирует только старший разряд  групп символов, определяющих значение  координаты  в двоичной форме. Например, в блоке 8 зафиксированы следующие данные:

•   комбинация оценок      … ] 7 6 4 4 5      6 4 6 4 7      7 8 8 8 8  [ … ;
•   комбинация символов  … ] 1 0 0 0 1      1 1 1 1 1      0 0 0 0 1  [ … .

Это означает, что старший разряд координаты = 111112= 3110  имеет индекс достоверности равный  6, а старший разряд координаты  = 12 =110 имеет индеек достоверности равный 7. На этом основании в блоке  8 принимается решение о передаче этих сведений в блок сравнения 10. В случае фиксации для старшего разряда координаты  низкого индекса достоверности осуществляется попытка повышения индекса за счет логарифма отношения правдоподобия аналогично тому как это делалось для символов, определяющих номер кластера. Если такая попытка завершается неудачей, все сведения о значениях координат предаются в блок инвариантных координат 9.

Блок инвариантных координат 9 определяет значения координат  и , принимая левые символы каждой координаты за младшие разряды.  В этом случае   = 111112= 3110 и   = 000012 =1610, что соответствует обратной записи порождающего полинома . Эти данные передаются в блок сравнения 10.

Блок сравнения 10 удерживает в своей  памяти сведения о кластерах, прямых координатах комбинаций каждого кластера и инвариантных координатах. Например, для кластера 20 в памяти блока хранятся данные:

,; , , соответствует комбинации 101000011010010;

,; , ,  соответствует комбинации 101000100000011;

,;, , соответствует комбинации 101001010100001;

,;,, соответствует комбинации 101001101110000.

Объем необходимой памяти блока  в байтах оценивается выражением . В соответствии с координатами каждая комбинация на декартовой плоскости занимает зону, определяемую выражениями (4.6) и (4.7). Задачей декодера в указанных условиях является решение системы строгих  неравенств и определения области, к которой принадлежит кодовый вектор.

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

Блок исправления стираний 11 принимает окончательное решение о принятом кодовом векторе. Выход этого блока является информационным выходом декодера.

Таким образом, применение декодера с использованием метода кластерного анализа позволяет исправить  стираний в отличии от декодеров, использующих метрику Хэмминга, которые способны исправить  стираний. Сложность декодера не зависит от кратности исправляемых ошибок, а объемы памяти для большинства кодов, применяемых на практике определяются соотношением (2n-8×n) не представляют трудностей с точки зрения их реализации.