ДЕКОДЕР С ОБРАБОТКОЙ СПИСКА БАЗОВОГО КЛАСТЕРА
DECODER WITH BASIC CLUSTER LIST PROCESSING

Изобретение относится к технике связи и может использоваться при проектировании новых и модернизации существующих систем передачи дискретной информации.
Известны устройства восстановления стираний и исправления ошибок, использующие индексы мягких решений символов для повышения вероятности правильного приема информации (см. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. - М.: Техносфера, 2005, С. 103-105; а также устройства по патентам РФ на изобретения №№2166235; 2209519; 2209520; 2256294; 2344556; 2490804).
Кроме того, известны устройства декодирования по упорядоченным статистикам (см. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. - М.: Техносфера, 2005, С. 213-216).
Наиболее близким устройством такого же назначения является декодер с упорядоченной статистикой символов (см. патент РФ на изобретение №2490804), содержащий блок приема, первый выход которого подключен к анализатору сигналов, а также накопитель, блок определения кластера и накопитель кодовой комбинации, один выход которого подключен к первому входу блока исправления стираний, отличающийся тем, что введены блок специальных оценок, блок специальных символов, блок упорядочения оценок, блок запрещенных комбинаций, блок эквивалентного кода, формирователь укороченного кода и блок корректирующего вектора, при этом второй выход блока приема подключен к входу блока специальных символов, один выход которого подключен к входу накопителя кодовой комбинации, а другой соединен с первым входом блока определения кластера, при этом второй вход этого блока подключен к одному выходу блока специальных оценок, тогда как другой выход этого блока подключен через последовательно соединенные накопитель и блок упорядочения оценок к первому входу блока эквивалентного кода, служебный выход которого подключен к входу блока запрещенных комбинаций, а выход этого блока подключен к служебному входу блока эквивалентного кода, выход которого подключен ко второму входу блока исправления стираний, при этом второй вход блока эквивалентного кода через формирователь укороченного кода подключен к первому выходу блока корректирующего вектора, а один вход этого блока подключен к выходу блока определения кластера, тогда как другой вход блока корректирующего вектора подключен к другому выходу накопителя кодовой комбинации, а выход блока корректирующего вектора подключен к третьему входу блока исправления стираний.
К недостаткам работы аналогов, в том числе и прототипа, предлагаемого декодера следует отнести не полное использование введенной в код избыточности из-за применения метрики Хэмминга, не учитывающей спектральные характеристики кода, необходимость поиска обратной матрицы в процедуре перестановочного декодирования по значениям индексов мягких решений (ИМР) для оценки возможности перехода к комбинациям эквивалентного кода. Это приводит к тому, что с увеличением кратности исправляемых кодом ошибок вычислительная сложность декодера приобретает экспоненциальный характер.
8
Технический результат - повышение достоверности приема информации и скорости обработки данных. Структурная схема декодера представлена на фигуре 1. Для достижения технического результата в декодер с обработкой списка базового кластера, содержащий блок 1 приема, первый выход которого через один выход блока 2 формирования индексов мягких решений подключен к первому входу блока 3 определения номера кластера, тогда как второй выход блока 1 приема через накопитель 10 кодовых комбинаций подключен к первому входу блока 13 коррекции ошибок, в который дополнительно введены блок 4 проверки номера кластера, блок 5 ключевых комбинаций, блок 6 перехода в базовый кластер, блок 7 базового кластера, блок 8 проверки линейности, блок 11 транспонирования матрицы перестановок, блок 9 выделения ошибок, блок 12 обратной перестановки, при этом первый выход блока 3 определения номера кластера подключен к входу блока 4 проверки номера кластера, а выход этого блока 4 подключен ко второму входу блока 3 определения номера кластера, второй выход которого через блок 5 ключевых комбинаций подключен к первому входу блока 6 перехода в базовый кластер, первый выход этого блока 6 через блок 7 базового кластера подключен к входу блока 8 проверки линейности, тогда как его один выход через блок 9 выделения ошибок подключен к первому входу блока 12 обратной перестановки, при этом другой выход блока 8 проверки линейности подключен к одному входу блока 11 транспонирования матрицы перестановок, а выход этого блока 11 подключен ко второму входу блока 12 обратной перестановки и выход этого блока 12 подключен ко второму входу блока 13 коррекции ошибок, при этом третий выход блока 8 проверки линейности подключен ко второму входу блока 6 перехода в базовый кластер, второй выход которого подключен к другому входу блока 11 транспонирования матрицы перестановок, при этом третий вход блока 6 перехода в базовый кластер подключен к другому выходу блока 2 формирования индексов мягких решений. Работа декодера с обработкой списка базового кластера иллюстрируется на примере кода БЧХ (15, 5, 7) с порождающим полиномом g(x)=2467 и порождающей матрицей G вида:
а
а
a
а
а
a
а
а
1
2,
3
7
5
8
11
15
f
3
k-f
k-f
2
Множество кодовых комбинаций кода разбивается на кластеры путем выделения f любых разрядов, где 1<f≤k. Пусть f=3 и в качестве разрядов любого кластера в системе выделяются разряды ,  (см. таблицу 1). Полное множество комбинаций кода, разбитое на кластеры в соответствие с выбранным правилом, представлено в таблицах 1-8, а номера всех кластеров в двоичной системе счисления образуют множество элементов поля GF(2)=GF(2). Кластер с номером ноль называется базовым. Анализ элементов столбцов кластеров показывает, что не всегда сочетание столбцов при их перестановке, в соответствии со значениями ИМР, приводит к образованию полного набора элементов поля GF(2), а значит подобное сочетание столбцов не может привести к одному из образцов эквивалентного кода и поэтому должно быть заменено на другое сочетание путем итеративных преобразований ближайших соседних столбцов. Например, столбец  в сочетании по отдельности со столбцами , ,  и  не обеспечивает получение полного набора элементов поля GF(2)=GF(2). Признаком неудачного сочетания столбцов является отсутствие элементов единичной матрицы. Число подобных неудачных сочетаний по значениям ИМР для всех столбцов составляет около 20% от общего возможного числа комбинаций столбцов. В случае необходимости столбец, стоящий на правой крайней позиции из числа элементов n-k заменяется на столбец, стоящий на первой позиции из числа избыточных элементов, и так далее. Как правило, неудачное сочетание столбцов устраняется за одну итерацию.
a
а
а
а
a
a
8
8
1
2
3
8
Заметно, что столбец  всех кластеров при любом сочетании не обеспечивает получение желаемого результата, поэтому разряд  целесообразно отвести под бит проверки четности номера кластера, при этом соотношение ⊕⊕= выполняется для всех кластеров. Для других кодов или при иной нумераций кластеров, подобное соотношение устанавливается по структуре базового кластера.
Пусть на выходе кодера образовался вектор вида
а
а
а
а
1
2
3
8
код
пер
код
пер
С учетом свойства ⊕⊕= V=V, т.е. переданный по каналу связи вектор в точности соответствует вектору V. Пусть в ходе передачи вектора V в канале связи действовал вектор ошибок вида
пер
ош
пр
Блок приема 1 принимает вектор вида V⊕V=V:
пр
а блок формирования индексов мягких решений (ИМР) 2 для каждого бита из V сформирует целочисленные значения индексов (см. Гладких, А.А. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи / А.А. Гладких. - Ульяновск: УлГТУ, 2010. - 379 с., см. с. 212).
а
а
а
а
а
а
а
1
2
3
8
пр
1
2
3
пр.
В блок определения номера кластера 3 выделяются символы и их индексы =0 с индексом 5; =0 с индексом 3; =1 с индексом 6 и =0 с индексом 6. Жесткие решения V фиксируются в накопителе 10 кодовых комбинаций и в блоке 6 перехода в базовый кластер. В блоке 3 определения номера кластера, а в блоке 4 проверки номера кластера осуществляется проверка соответствия символов номера кластера (позиции  и , ) правилу четности. Если правило четности выполняется, декодер реализует последующие шаги по восстановлению вектора V В противном случае номер кластера восстанавливается за счет взаимодействия блока 3 и блока 4 декодера с использованием арсенала итеративных преобразований в соответствии с правилом
1
2
где функция  возвращает знак своего аргумента; L(d) - оценка надежности символа, участвующего в формировании проверочного бита; L(d) - оценка надежности проверочного символа; µ - число исключенных из преобразований единичных символов при условии, что они имеют высокий показатель ИМР.
а
а
а
а
а
1
2
3
3
3
Например, в полученной последовательности , ,  символ =1 с индексом 6 является наиболее надежным. Информационное значение =1, поэтому µ=1. Последовательность, подлежащая коррекции, принимает вид: -5 -3 | -6. В этой последовательности единицы представляются знаком +, а нули знаком -, вертикальная черта отделяет символ четности -6 от символов номера кластера.
На первом шаге итеративных преобразований получаем:
1
L(d)=[-3+0] | -6≈3 - новое значение апостериорной оценки для символа - 5;
2
L(d)=[-5+0] | -6≈5 - новое значение для символа -3.
Второй шаг итерации:
1
L(d)=[-3+-5] | -6≈-2 - значение коррекции для символа -5;
2
L(d)=[-5+3] | -6≈2 - значение коррекции для символа +4.
Третий шаг итерации:
1
L(d)=[-3+2] | -6≈1 - значение коррекции для символа -5;
2
L(d)=[-5-2] | -6≈6 - значение коррекции для символа +4.
2
10
Итогом преобразований являются действия (-5+1=-4) и (-3+6=+3). В результате вместо искаженной последовательности -5 -3 +6 | -6 получают восстановленную последовательности символов -4 +3 +6 | -6. Следовательно, номер кластера, которому принадлежит комбинация, имеет номер 011=3.
2
10
пр
3
Блок 5 ключевых комбинаций, получив проверенное значение кластера 011=3 определяет для V, принадлежащего третьему кластеру, ключевую комбинацию этого кластера путем умножения вектора V=01100 на порождающую матрицу σ. В результате формируется ключевая комбинация
пр
кл3
В блоке 6 перехода в базовый кластер комбинация V с восстановленным номером кластера путем поразрядного сложения с комбинацией V формируют комбинацию, принадлежащую базовому кластеру
0
ранж
1
2
3
а
а
а
Путем ранжирования символов V по убыванию их ИМР в блоке 6 ключевых комбинаций формируется ранжированный вектор V, в котором не учитываются символы номера кластера , , .
ранж
2
10
На основании процедуры формирования V в блоке 6 декодера формируется матрица перестановок Р размерности (n-f)×(n-f). В блоке 7 базового кластера путем умножения комбинаций (матрицы) кластера на Р получают конфигурацию комбинации вида (переставленный кластер 000=0):
а
а
а
a
а
а
а
а
11
12
12
13
11
12
ранж
11
12
В блоке 8 проверки линейности оценивается результат перестановки путем выделения столбцов на позициях крайних левых разрядов (в примере позиции  и ) и выявлением признаков единичной матрицы (обратной единичной матрицы). Если условие не выполняется в блоках 6 и 7, производится замена  на  и так далее до тех, пор пока не выполнится условие образования единичной матрицы. В примере условие выполняется (см. нижние две строки на позициях и ). Выделения ошибок происходит в блоке 9 выделения ошибок путем сравнения вектора V, у которого совпадаю элементы  и  с элементами второй строки переставленных комбинаций нулевого кластера, по сути с эталонным переставленным вектором
10
<mrow><msubsup><mi>V</mi><mrow><mi>о</mi><mi>ш</mi></mrow><mo>,</mo></msubsup></mrow>
Этот вектор выделяется из строк переставленного кластера 0. Сравнение приводит к образованию переставленного вектора ошибок
.
T
<mrow><msubsup><mi>V</mi><mrow><mi>о</mi><mi>ш</mi></mrow><mo>,</mo></msubsup><mo>×</mo><msup><mi>P</mi><mi>T</mi></msup></mrow>
В блоке 11 транспонирования матрицы перестановок из матрицы Р получают матрицу P и с учетом добавленных символов номера кластера обрабатывают вектор
, получая истинный вектор ошибок после обратных перестановок, выполняемых в блоке 12
Декодирование завершается в блоке 13 путем сложения принятого вектора с найденным вектором ошибки
Предложенный декодер позволяет:
- в большинстве случаев исправлять стирания, кратность которых определяется соотношением n-k;
- по сравнению с аналогами существенно сократить время обработки кодовых комбинаций в декодере за счет исключения из вычислительного процесса процедуры поиска обратной матрицы для переставленной порождающей матрицы: кода и последующего формирования на этой основе матрицы эквивалентного кода;
- декодер работает только с базовым кластером (всегда с единственным списком), не затрачивая при обработке каждого нового принятого вектора время на составление нового списка методом подбора наиболее вероятных векторов.