Синтез функциональных схем кодека, реализующего синдромный алгоритм декодирования кодов Рида-Маллера

Выполним синтез структурных схем кодека, реализующего синдромный алгоритм декодирования кода РМ со следующими исходными данными: m = 5 и Е = 3.

Определим остальные параметры кода, а именно:

– длину кода: n = 2^m = 2⁵ = 32 двоичных символа;

– количество двоичных символов в информационном блоке:

– количество проверочных символов l = n-k = 32-26 = 6,

– минимальное кодовое расстояние d = 2^m-E = 2^5-3 = 4.

Таким образом, код РМ третьего порядка (Е=3) имеет следующие параметры: (n,k,d₀) = (32,26,4) и задается порождающей матрицей вида:

Порождающие матрицы G₀(x),…,G₃(x) формируем в соответствии с методикой рассмотренной в разделе 3.5.2.

Порождающая матрица G₀(x) содержит одну строку, состоящую из 32 логических единиц, т. е.:

G₀(x)=[11111111111111111111111111111111]=[а₀].

Порождающая матрица G₁(x) содержит пять строк и имеет следующую структуру:

=

Порождающая матрица G₂(x) содержат 10 строк и имеет следующую структуру:

=

Порождающая матрица G₃(x) также содержат 10 строк и имеет следующую структуру:

=

Следовательно, порождающая матрица G(x) кода РМ с данными параметрами будет иметь следующую структуру:

Так как коды РМ относятся к классу несистематических кодов, то для реализации алгоритма синдромного декодирования необходимо построенную порождающую матрицу G_26,32(x) привести к каноническому или ступенчато-приведенному виду.

Для этого необходимо в порождающей матрице G_26,32(x) выполнить следующие операции: перестановку столбцов (1 – знак операции), перестановку строк (2 – знак операции) и суммирование по модулю два символов строк (М2 – знак операции).

Данные операции приведены в таблице 3.1.

Таблица 3.1 – Тип и последовательность операций, выполняемых над строками и столбцами порождающей матрицы G_26,32(x)

В результате выполнения данных операций формируется порождающая матрица канонического типа, т. е. порождающая матрица G_26,32(x) = │1:Р│, представленная ниже.

Сформированная порождающая матрица позволяет построить транспонированную проверочную матрицу Н^Т_6,32(х), которая имеет следующий вид или структуру:

Н^Т_6,32(х) =

Ненулевые символы строк данной матрицы определяют позиции информационных символов (а₁…а₂₆), участвующие в формировании проверочных символов (b₁…b₆).

Синтез структурной схемы кодирующего устройства (кодера) выполняем с определения основных его функций. Основными функциями кодера являются:

– разделение символов входного информационного потока на 26 параллельных подпотоков;

– формирование проверочных символов, образующих шесть параллельных подпотоков;

– объединение символов 32 параллельных подпотоков в единый кодовый поток, т. е. формирование и передача символов кодовой последовательности в последовательном коде.

Для реализации данных функций в кодере необходимо иметь следующие функциональные блоки: КРИ-1/26-коммутатор распределения информации на 26 параллельных подпотоков, ФПСк – формирователь проверочных символов кодера, КОИ-32/1 – коммутатор объединения 32 параллельных подпотоков в последовательный кодовый поток F(x) и БСК блок синхронизации кодера, содержащего делитель частоты на 26 и кольцевой счетчик на 32. В соответствии с этим структурная схема кодера будет иметь следующее построение (рисунок 3.21)

Рисунок 3.21 – Структурная схема кодера кода Рида-Маллера с параметрами (n,k,d₀) = (32,26,4)

Кодирование информации производится следующим образом. После преобразования передачи информации из последовательного кода в параллельный код 26 информационных символов поступают одновременно на соответствующие входы КОИ-32/1 и ФПСк. В ФПСк проверочные символы b₁…b₆ формируются в соответствии с транспонированной проверочной матрицей Н^Т_6,32(х), а именно:

b₁ = a₁ Å a₂ Å a₃ Å a₄ Å a₅ Åa₇ Åa₈ Å a₉ Å a₁₁ Å a₁₂ Åa₁₃ Å a₁₇ Å a₁₈ Å a₂₀ Å a₂₃ = a_27;

b₂ = a₁ Å a₂ Å a₃ Åa₄ Å a₆ Å a₇ Å a₈ Å a₁₀ Å a₁₄ Å a₁₅ Åa₁₇ Å a₁₉ Å a₂₁ Å a₂₄ = a_28;

b₃ = a₁ Å a₂ Å a₃Å a₅Å a₆Å a₇ Å a₉ Å a₁₀Å a₁₂ Å a₁₄ Å a₁₆ Å a₁₈ Å a₁₉ Åa₂₂ Å a₂₅ = a_29;

b₄ = a₁ Å a₂ Å a₄ Å a₅ Åa₆ Å a₈Å a₉Å a₁₀Å a₁₃ Å a₁₅ Å a₁₆ Å a₂₀ Å a₂₁ Å a₂₂ Å a₂₆ = a_30;

b₅ = a₂ Å a₅Å a₇Åa₈Åa₁₀Å a₁₂Åa₁₃Åa₁₄Å a₁₆Åa₁₇Å a₁₉Å Å a₂₁Å a₂₃Åa₂₄Åa₂₅Å a₂₆ = a₃₁

b₆ = a₁ Å a₅Å a₇Å a₈Å a₁₀Å a₁₁Å a₁₄Å a₁₅Å a₁₈Å a₂₀Å a₂₂Å a₂₃Å a₂₄Å a₂₅Å a₂₆ = a₃₂

ФПСк может быть выполнен либо с помощью сумматоров по модулю два (двухвходовые схемы «Исключающее ИЛИ»), либо с помощью многовходовых схем контроля честности. КРИ-1/26 и КОИ-32/1 могут быть выполнены по принципу построения рассмотренному в разделе 3.2.1.

В этом случае сигналы управления (С₁…С₅) мультиплексором будут представлять собой кодовые слова (комбинации) содержащие пять символов.

Синтез структурной схемы декодирующего устройства (декодера), реализующего синдромный алгоритм декодирования кода Рида-Маллера, выполняем по методике рассмотренной в подразделе 3.5.2. Реализация алгоритма синдромного декодирования сводится к выполнению следующих основных операций: формирование синдрома, дешифрация синдрома, коррекция ошибок. В соответствии с матрицей Н^Т_6,32 (х) синдром будет представлять кодовое слово, содержащее шесть символов, структура которых, при наличии ошибок, будет совпадать со структурой соответствующего столбца данной матрицы, т. е. Н^Т_6,32(х). Синдром может быть сформирован различными способами. Например, как произведение кодовой последовательности F' (х) на транспонированную проверочную матрицу Н^Т_6,32(х), т.е. S(x) = F'(х)-Н^Т_32,6(х) или как S(x)=(b₁Åb'₁), (b₂Åb'₂),…,(b₆Åb'₆), где b'₁,…,b'₆ – проверочные символы, сформированные из принятых информационных символов (а'₁,…,а'₂₆) по алгоритму (правилу) аналогично используемому в кодере. Основными функциями декодера, реализующего алгоритм синдромного декодирования являются:

– преобразование кодовых символов последовательности F'(х) из последовательного кода в параллельный код;

– формирование проверочных символов b'₁…b'₆ из принятых информационных символов;

– формирование синдромных символов S₁…S₆ по правилу: S₁=(b₁Åb'₁),

S₂=(b₂Åb'₂), S₃=(b₃Åb'₃), S₄= (b₄Åb'₄), S₅=(b₅Åb'₅), S₆= (b₆Åb'₆);

– дешифрация синдрома;

– коррекция ошибок;

– преобразование информационных символов а₁…а₂₆ из параллельного кода в последовательный и выдача их получателю.

Рисунок 3.22 – Структурная схема декодера, реализующего синдромный алгоритм декодирования кода Рида-Маллера с параметрами (32,26,4)

Для реализации данных функций в декодере необходимо иметь следующие функциональные блоки: КРИ-1/32 – коммутатор распределения информации на 32 параллельных подпотока, ФПСс – формирователь проверочных символов декодера, ФСС – формирователь синдромных символов, ДШС – дешифратор синдрома, КО – корректор ошибок, КОИ-26/1 – коммутатор объединения информации 26 параллельных подпотоков в единый поток и БСД – блок синхронизации декодера в составе делителя частоты на 32 и кольцевого счетчика на 26. Структурная схема декодера приведена на рисунок 3.22. Корректор ошибок на данном рисунке представлен в виде совокупности 26-ти двухвходовых сумматоров по модулю два.

Формирователь синдромных символов выполняется в виде шести двухвходовых сумматоров по модулю два.

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

3.6 Коды Рида-Соломона: определение, параметры, матричное представление, алгоритмы декодирования и синтез структурных схем кодека