Синтез кодека циклического кода с формированием системы связанных проверок

Разработать кодек циклического кода, реализующего мажоритарный алгоритм декодирования и полностью реализующий минимальное кодовое расстояние d₀ при формировании системы раздельных проверок, можно не для всех кодов. Это определяется условием, которое накладывается на систему раздельных проверочных подматриц (3.5), а именно: декодируемый информационный символ входит во все проверочные уравнения, а все другие символы входят только в одно проверочное уравнение.

Для кодов, которые не допускают формирование СРП, необходимо «ослабить» условие, накладываемое на формируемые проверочные уравнения, т. е. допустить вхождение недекодируемых символов в два, три и т. д. проверочных уравнения. Пусть каждый символ, кроме декодируемого а'_i, может входить не более чем в ε_с проверочных уравнений. В этом случае одиночная ошибка исказит не более ε_с проверочных уравнений, а t (t≥2)- кратная ошибка исказит не более t∙ε_с проверочных уравнений. Параметр ε_с называется коэффициентом связности проверочных равнений, а сформированные соответствующие проверочные уравнения образуют систему связанных проверочных уравнений (ССП).

При ε_с связанных проверочных уравнениях проверочная подматрица cодержит в i -ой строке только единичные символы, а в остальных строках – не более ε_с единичных символов. В общем ССП представляет собой обобщение СРП, для которой ε_с =1.

Для реализации кодового расстояния (d_p), равного минимальному кодовому расстоянию, т. е. d_p = d₀, достаточно иметь не более

μ_max = ε_с(d_p-2)+1 (3.9) (3.9)

нетривиальных проверочных уравнений.

Минимально реализуемое кодовое расстояние при ССП равно или более

d_pmin ≥ [(μ-1)/ ε_с]+2, (3.10) (3.10)

где [(μ-1)/ ε_с] – означает ближайшее меньшее целое число.

Если при числе исправляемых ошибок t_исп< d_p-1, кроме декодируемого символа а_i существует t' символов, искажение которых вызывает нарушение t'∙ε_с проверочных уравнений, то в этом случае имеем систему связанных уравнений, так называемых, первого типа (ССП₁), а в противном случае имеем систему связанных проверок второго типа (ССП₂). Для ССП₂ число искаженных проверочных уравнений не больше, чем для ССП₁ при одинаковых значениях t и ε_с; при ε_с = 1 ССП₂ не существует. Потому условие (3.9), оставаясь достаточным, не является необходимым. Действительно, если t -кратная ошибка нарушает менее t'∙ε_с уравнений, то при d_p=2∙t+1 для исправления t' ≤ t ошибок надо иметь μ < ε_с(d_p-2)+1 проверочных уравнений.

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

В качестве ЦК выбираем (n,k,d₀)=(7,4,3) – код Хэмминга порождающим полиномом Р(х)=х³+х²+1 для которого невозможно составить СРП.

Для формирования ССП принимаем коэффициент связности равным двум, т. е. ε_с = 2. Определяем проверочный полином

h(x) = (xⁿ+1)/P(x) = (x⁷+1)/(х³+х²+1) = х⁴+х³+х²+1 = 1+х²+х³+х⁴ = = 10111.

Строим транспонированную проверочную матрицу следующим образом:

1) в качестве первого столбца записываем проверочный полином, представленный в двоичной форме и дополняем его нулевыми символами до n=7;

2) производим (l-1)=(3-1)=2 последовательных циклических сдвига вниз двоичных символов первого столбца. В результате получаем следующую транспонированную проверочную матрицу:

H ^T_7,3(x) = (3.11)

Используя данную подматрицу строим проверочную подматрицу θ_1.1(х) следующим образом:

1) первый столбец проверочной подматрицы θ_1.1(х) повторяет первый столбец матрицы (3.11);

2) символы второго и третьего столбцов формируются путем суммирования по модулю два двоичных символов соответственно первого плюс второго и первого плюс третьего столбцов матрицы (3.11);

3) символы четвертого столбца формируются путем суммирования по модулю два двоичных символов первого, второго и третьего столбцов матрицы (3.11).

В результате получаем следующую проверочную подматрицу:

(3.12)

Из структуры данной подматрицы видно, что только первая строка состоит из ненулевых символов, т. е. 1, а все остальные строки содержат не более двух единиц. Следовательно, данная проверочная подматрица образует ССП с коэффициентом связности ε_с=2 и позволяет сформировать следующую ССП:

а₁Åа₃Åа₄Åа₅

а₁Åа₂Åа₃Åа₆

а₁Åа₄Åа₆Åа₇

а₁Åа₂Åа₅Åа₇. (3.13)

В данном случае μ=4 и на основании формулы (3.10) реализуемое кодовое расстояние d_p=d₀=3. Однако, согласно формуле (3.9), достаточно использовать μ=3 проверочных уравнений и плюс тривиальное проверочное уравнение а₁=а'₁.

Следовательно, одно проверочное уравнение из ССП (3.13) можно исключить. Опустим проверочное уравнение вида а₁Åа₄Åа₆Åа₇.

Таким образом, для синтеза функциональной схемы декодера используем следующую ССП:

S₁ = а₁= а'₁

S₂ = а₃Åа₄Åа₅

S₃ = а₂Åа₃Åа₆

S₄ = а₂Åа₅Åа₇.

Основными функциональными блоками декодера являются: последовательный регистр сдвига, содержащий n=7 ячеек памяти, блок формирования ССП (совокупность сумматоров по модулю два), мажоритарный элемент (МЭ), коммутатор (К), ключи управления (Кл) и формирователь сигналов управления ключами. В соответствии с этим обобщенная функциональная схема декодера будет иметь построение, представленное на рисунке 3.7.

Рисунок 3.7 – Обобщенная функциональная схема декодера при формировании ССП и ε_с=2

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

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

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

Наряду с существованием СРП и ССП могут быть квазираздельные и квазисвязанные проверочные уравнения. Квазираздельные проверочные уравнения представляют собой уравнения относительно линейной комбинации (суммы по модулю два) любых символов. Для этого «ν» (ν≥1) строк в матрице θ_ν,1, соответствующих номерам этих символов, должны содержать не более одного единичного элемента. Для данных уравнений также сохраняется свойство цикличности относительно всех символов, входящих в определенную линейную комбинацию. Квазисвязанные проверочные уравнения – это такие проверочные уравнения, при которых матрица θ_ν,ε_с в ν (ν≥1) строках содержит только единичные символы, а в остальных строках – не более ε_с единичных символов.

Кроме рассмотренных способов формирования проверочных уравнений разработан способ ортогонализации проверочных уравнений в L (L ≥ 2) шагов или этапов, а также алгоритм декодирования, основанный на способе последовательной редукции кода. С данными алгоритмами декодирования можно познакомиться в монографии [4]. Достоинством алгоритма мажоритарного декодирования является минимальная задержка информации при декодировании, которая составляет (n+k) тактов; n тактов при записи информации в регистр сдвига декодера; k тактов при выдаче информации.