Декодер с обработкой списка базового кластера

Изобретение относится к технике связи и может использоваться при проектировании новых и модернизации существующих систем передачи дискретной информации. Технический результат изобретения заключается в повышении достоверности приема информации и скорости обработки данных. Декодер позволяет исправлять стирания, кратность которых определяется соотношением n-k; существенно сократить время обработки кодовых комбинаций в декодере за счет исключения из вычислительного процесса процедуры поиска обратной матрицы для переставленной порождающей матрицы кода и последующего формирования на этой основе матрицы эквивалентного кода; декодер работает только с базовым кластером (всегда с единственным списком), не затрачивая при обработке каждого нового принятого вектора время на составление нового списка методом подбора наиболее вероятных векторов. 1 ил., 8 табл.

 

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

Известны устройства восстановления стираний и исправления ошибок, использующие индексы мягких решений символов для повышения вероятности правильного приема информации (см. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. - М.: Техносфера, 2005, С. 103-105; а также устройства по патентам РФ на изобретения №№2166235; 2209519; 2209520; 2256294; 2344556; 2490804).

Кроме того, известны устройства декодирования по упорядоченным статистикам (см. Р. Морелос-Сарагоса. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. - М.: Техносфера, 2005, С. 213-216).

Наиболее близким устройством такого же назначения является декодер с упорядоченной статистикой символов (см. патент РФ на изобретение №2490804), содержащий блок приема, первый выход которого подключен к анализатору сигналов, а также накопитель, блок определения кластера и накопитель кодовой комбинации, один выход которого подключен к первому входу блока исправления стираний, отличающийся тем, что введены блок специальных оценок, блок специальных символов, блок упорядочения оценок, блок запрещенных комбинаций, блок эквивалентного кода, формирователь укороченного кода и блок корректирующего вектора, при этом второй выход блока приема подключен к входу блока специальных символов, один выход которого подключен к входу накопителя кодовой комбинации, а другой соединен с первым входом блока определения кластера, при этом второй вход этого блока подключен к одному выходу блока специальных оценок, тогда как другой выход этого блока подключен через последовательно соединенные накопитель и блок упорядочения оценок к первому входу блока эквивалентного кода, служебный выход которого подключен к входу блока запрещенных комбинаций, а выход этого блока подключен к служебному входу блока эквивалентного кода, выход которого подключен ко второму входу блока исправления стираний, при этом второй вход блока эквивалентного кода через формирователь укороченного кода подключен к первому выходу блока корректирующего вектора, а один вход этого блока подключен к выходу блока определения кластера, тогда как другой вход блока корректирующего вектора подключен к другому выходу накопителя кодовой комбинации, а выход блока корректирующего вектора подключен к третьему входу блока исправления стираний.

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

Технический результат - повышение достоверности приема информации и скорости обработки данных. Структурная схема декодера представлена на фигуре 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 вида:

Множество кодовых комбинаций кода разбивается на кластеры путем выделения f любых разрядов, где 1<f≤k. Пусть f=3 и в качестве разрядов любого кластера в системе выделяются разряды а ₁, а _2, a ₃ (см. таблицу 1). Полное множество комбинаций кода, разбитое на кластеры в соответствие с выбранным правилом, представлено в таблицах 1-8, а номера всех кластеров в двоичной системе счисления образуют множество элементов поля GF(2^f)=GF(2³). Кластер с номером ноль называется базовым. Анализ элементов столбцов кластеров показывает, что не всегда сочетание столбцов при их перестановке, в соответствии со значениями ИМР, приводит к образованию полного набора элементов поля GF(2^k-f), а значит подобное сочетание столбцов не может привести к одному из образцов эквивалентного кода и поэтому должно быть заменено на другое сочетание путем итеративных преобразований ближайших соседних столбцов. Например, столбец а ₇ в сочетании по отдельности со столбцами а ₅, a ₈, а ₁₁ и а ₁₅ не обеспечивает получение полного набора элементов поля GF(2^k-f)=GF(2²). Признаком неудачного сочетания столбцов является отсутствие элементов единичной матрицы. Число подобных неудачных сочетаний по значениям ИМР для всех столбцов составляет около 20% от общего возможного числа комбинаций столбцов. В случае необходимости столбец, стоящий на правой крайней позиции из числа элементов n-k заменяется на столбец, стоящий на первой позиции из числа избыточных элементов, и так далее. Как правило, неудачное сочетание столбцов устраняется за одну итерацию.

Заметно, что столбец a ₈ всех кластеров при любом сочетании не обеспечивает получение желаемого результата, поэтому разряд а ₈ целесообразно отвести под бит проверки четности номера кластера, при этом соотношение а ₁⊕а ₂⊕a ₃=a ₈ выполняется для всех кластеров. Для других кодов или при иной нумераций кластеров, подобное соотношение устанавливается по структуре базового кластера.

Пусть на выходе кодера образовался вектор вида

С учетом свойства а ₁⊕а ₂⊕а ₃=а ₈ V_код=V_пер, т.е. переданный по каналу связи вектор в точности соответствует вектору V_код. Пусть в ходе передачи вектора V_пер в канале связи действовал вектор ошибок вида

Блок приема 1 принимает вектор вида V_пер⊕V_ош=V_пр:

а блок формирования индексов мягких решений (ИМР) 2 для каждого бита из V_пр сформирует целочисленные значения индексов (см. Гладких, А.А. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи / А.А. Гладких. - Ульяновск: УлГТУ, 2010. - 379 с., см. с. 212).

В блок определения номера кластера 3 выделяются символы и их индексы а ₁=0 с индексом 5; а ₂=0 с индексом 3; а ₃=1 с индексом 6 и а ₈=0 с индексом 6. Жесткие решения V_пр фиксируются в накопителе 10 кодовых комбинаций и в блоке 6 перехода в базовый кластер. В блоке 3 определения номера кластера, а в блоке 4 проверки номера кластера осуществляется проверка соответствия символов номера кластера (позиции а ₁ и а ₂, а ₃) правилу четности. Если правило четности выполняется, декодер реализует последующие шаги по восстановлению вектора V_пр. В противном случае номер кластера восстанавливается за счет взаимодействия блока 3 и блока 4 декодера с использованием арсенала итеративных преобразований в соответствии с правилом

где функция возвращает знак своего аргумента; L(d₁) - оценка надежности символа, участвующего в формировании проверочного бита; L(d₂) - оценка надежности проверочного символа; µ - число исключенных из преобразований единичных символов при условии, что они имеют высокий показатель ИМР.

Например, в полученной последовательности а ₁, а ₂, а ₃ символ а ₃=1 с индексом 6 является наиболее надежным. Информационное значение а ₃=1, поэтому µ=1. Последовательность, подлежащая коррекции, принимает вид: -5 -3 | -6. В этой последовательности единицы представляются знаком +, а нули знаком -, вертикальная черта отделяет символ четности -6 от символов номера кластера.

На первом шаге итеративных преобразований получаем:

L(d₁)=[-3+0] | -6≈3 - новое значение апостериорной оценки для символа - 5;

L(d₂)=[-5+0] | -6≈5 - новое значение для символа -3.

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

L(d₁)=[-3+-5] | -6≈-2 - значение коррекции для символа -5;

L(d₂)=[-5+3] | -6≈2 - значение коррекции для символа +4.

Третий шаг итерации:

L(d₁)=[-3+2] | -6≈1 - значение коррекции для символа -5;

L(d₂)=[-5-2] | -6≈6 - значение коррекции для символа +4.

Итогом преобразований являются действия (-5+1=-4) и (-3+6=+3). В результате вместо искаженной последовательности -5 -3 +6 | -6 получают восстановленную последовательности символов -4 +3 +6 | -6. Следовательно, номер кластера, которому принадлежит комбинация, имеет номер 011₂=3₁₀.

Блок 5 ключевых комбинаций, получив проверенное значение кластера 011₂=3₁₀ определяет для V_пр, принадлежащего третьему кластеру, ключевую комбинацию этого кластера путем умножения вектора V₃=01100 на порождающую матрицу σ. В результате формируется ключевая комбинация

В блоке 6 перехода в базовый кластер комбинация V_пр с восстановленным номером кластера путем поразрядного сложения с комбинацией V_кл3 формируют комбинацию, принадлежащую базовому кластеру

Путем ранжирования символов V₀ по убыванию их ИМР в блоке 6 ключевых комбинаций формируется ранжированный вектор V_ранж, в котором не учитываются символы номера кластера а ₁, а ₂, а ₃.

На основании процедуры формирования V_ранж в блоке 6 декодера формируется матрица перестановок Р размерности (n-f)×(n-f). В блоке 7 базового кластера путем умножения комбинаций (матрицы) кластера на Р получают конфигурацию комбинации вида (переставленный кластер 000₂=0₁₀):

В блоке 8 проверки линейности оценивается результат перестановки путем выделения столбцов на позициях крайних левых разрядов (в примере позиции а ₁₁ и а ₁₂) и выявлением признаков единичной матрицы (обратной единичной матрицы). Если условие не выполняется в блоках 6 и 7, производится замена а ₁₂ на a ₁₃ и так далее до тех, пор пока не выполнится условие образования единичной матрицы. В примере условие выполняется (см. нижние две строки на позициях а ₁₁ и а ₁₂). Выделения ошибок происходит в блоке 9 выделения ошибок путем сравнения вектора V_ранж, у которого совпадаю элементы а ₁₁ и а ₁₂ с элементами второй строки переставленных комбинаций нулевого кластера, по сути с эталонным переставленным вектором

Этот вектор выделяется из строк переставленного кластера 0₁₀. Сравнение приводит к образованию переставленного вектора ошибок $$V_{ош}^{,}$$ .

В блоке 11 транспонирования матрицы перестановок из матрицы Р получают матрицу P^T и с учетом добавленных символов номера кластера обрабатывают вектор $$V_{ош}^{,}\times P^T$$ , получая истинный вектор ошибок после обратных перестановок, выполняемых в блоке 12

Декодирование завершается в блоке 13 путем сложения принятого вектора с найденным вектором ошибки

Предложенный декодер позволяет:

- в большинстве случаев исправлять стирания, кратность которых определяется соотношением n-k;

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

- декодер работает только с базовым кластером (всегда с единственным списком), не затрачивая при обработке каждого нового принятого вектора время на составление нового списка методом подбора наиболее вероятных векторов.

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