Мажоритарное декодирование

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

Существует три способа построения систем проверочных уравнений при мажоритарном декодировании:

• системы с разделенными проверками;

• системы с -связанными проверками;

• системы с квазиразделенными проверками.

В системах с разделенными проверкаминекоторый символ, относительно которого разделяется система уравнений, входит во все уравнения. Любой другой символ входит не более чем в одну проверку. Отсюда следует, что для коррекцииtошибок система должна состоять из (2t + 1) уравнений и иметь на столько же входов мажоритарные элементы.

Пример:Пусть имеется код (6; 3), задаваемый следующей проверочной матрицей:

а₁а₂а₃ а₄а₅а₆

0 1 1 1 0 0

H(x) =1 0 1 0 1 0

1 1 1 0 0 1

Запишем систему уравнений:

а₄= a₂a₃

а₅= a₁a₃

а₆= a₁a₂a₃

Из этой системы можно записать систему проверочных равенств, где равенство а_i=а_iназываетсяуравнением истинностиилитривиальным.

Для a₁: a₁= a₃a₅

а₁ = а₂a₃a₆=а₄a₆

а₁= a₁

Для a₂: a₂= a₃a₄

а₂ = а₁a₃a₆=а₅a₆

а₂= a₂

Для a₃: a₃= a₂a₄

а₃ = а₁a₅

а₃= a₃

Видно, что каждый из принятых символов a_iвходит в данные системы один раз, и, следовательно, если он ошибочен, то ошибочным будет одно из трех уравнений системы; два остальных– правильны. По большинству правильных проверок мажоритарный элемент принимает правильное решение об оценке состояния разряда.

С ростом числа корректируемых ошибок растет число уравнений в системе и, следовательно, увеличивается сложность мажоритарного элемента.

Декодер для кода (6,3) требует шесть сумматоров по модулю два и три мажоритарных элемента.

Схема мажоритарного декодера кода (6, 3) представлена на рисунке.

Рисунок – Схема мажоритарного декодера кода (6, 3)

Достоинства мажоритарного декодирования: простота реализации, высокая скорость декодирования.

Недостатки: такие декодеры могут декодировать малый класс кодов.

Циклические коды: общие сведения, определение

Важнейшим недостатком систематических линейных блоковых кодов (СЛБК) является высокая трудоемкость их построения при длине кодо­вой последовательности n≥31 двоичный символ и коррекции ошибок кратностью t_oш≥3 двоичных символа. Поиск более про­стых принципов построения СЛБК привел к открытию нового широкого класса групповых линейных блоковых кодов, полу­чивших название циклических кодов (ЦК).

Циклические коды являются подклассом в классе линейных блоковых кодов. Свое название коды получили из-за основной операции построения кодовых последовательностей (F_i (x)) – циклического сдвига (перестановки) двоичных символов разрешенных кодовых последовательностей.

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

Кодовую последовательность ЦК в общем виде можно записать так:

где х - формальная переменная,

п-1, п-2 ,..., 1, 0 — показатели степеней, в которые возво­дятся основания кодов, и одновременно порядковые номера, ко­торые занимают двоичные символы (разряды) кодовой последовательности, начиная со старшего и заканчивая нулевым;

c_i - коэффициенты формальной переменной, которые могут принимать значения или быть равными логической 1 (ненулевой член F_i(x)) или логического 0 (нулевой член F_i(x)). Например,

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

Уточним сущность понятия циклического сдвига или циклической перестановки двоичных символов кодовой после­довательности.

Пусть то циклический сдвиг на один разряд дает Чтобы степень новой кодовой последовательно­сти Fi(x) не превышала (п-1), член с_п-1х^п заменяется единицей, поэтому

Например, пусть при n=7двоичных символов. (Заметим, что запись кодовой последова­тельности в виде многочлена, а затем перевод ее в двоичную форму записи, не всегда определяет длину кодовой последова­тельности n. Например, при п=5, многочлен F(x) = х²+1=101, т.е. n=3, что неверно. В таких случаях надо дописать старшие нулевые символы, т.е. F(x)=x²+1=00101, что дает п=5 двоич­ным символам).

Сдвигаем F(x) на один разряд (символ) влево, и получаем F(x) =1011100=х⁶+ х⁴+ х³+х². Очевидно, что x^l(x⁵+x³+x²+x)=x⁵+x⁴+x³+x². Отсюда вытекает второе определение ЦК, а именно, циклический код – это код, для которого циклический сдвиг двоичных символов разрешенной кодовой последовательности влево или вправо на один, два,...., (k-1) символов вновь приводит к формированию разрешенной кодовой последовательности.

Таким образом, циклическую перестановку двоичных символов разрешенной кодовой последовательности можно рас­сматривать как умножение F(x) на х при первом сдвиге, на х² при втором сдвиге и т. д., что можно в общем виде записать или представить так:

Таким образом, можно сделать следующие выводы:

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

2. ЦК относятся к групповым линейным кодам, если они образуются путем умножения каждой последовательности равнодоступного (простого) кода, выраженных в виде многочлена Q(x) с максимальной степенью (k-1), на некоторой полином Р(х) степени l=n-k.

Информационный полином: Q(x)=a_k-1x^k-1+ a_k-2x^k-2+…+ a₀x⁰

Порождающий (образующий) полином: P(x)=b_l x^l+ a_l-1 x^l-1+…+ b₀x⁰

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

В качестве образующего полинома используются полиномы, обладающие следующими свойствами:

1. образующий полином Р(х) должен быть делителем двучлена х^п+1;

2. образующий полином не должен раскладываться на сомножители более низких степеней, и должен делиться без ос­татка на самого себя и на 1, т.е. на х°;

3. максимальная степень образующего полинома должна быть равной l=n-k, т.е. соответствовать количеству прове­рочных символов используемого кода.