Разработка методов мажоритарного декодирования с улучшенными вероятностно-временными характеристиками (стр. 3 из 9)
.Например, при использовании одного избыточного элемента (r= 1) часть опознанных ошибок составляет
.Для того чтобы искаженная кодовая комбинация была опознана с наименьшей ошибкой, необходимо чтобы остальные
запрещенных комбинаций были разбиты на 
непересекающихся множеств 
, причем 
кодовые комбинации, принадлежащие 
, должны в наибольшей степени быть похожими на i-ю разрешенную комбинацию и должны быть приписаны ей.Процедура опознания искаженной кодовой комбинации в этом случае будет состоять в ее сравнении со всеми
кодовыми комбинациями. Когда произойдет совпадение с одной из комбинаций, принадлежащих , осуществится отождествление искаженной комбинации с i-й разрешенной, т.е. исправление ошибки. Ошибка будет исправлена в случаях из всех возможных. Отношение числа исправляемых кодом ошибочных кодовых комбинаций к числу обнаруживаемых ошибочных комбинаций равно [5, 67]: 
.Степень отличия любых двух кодовых комбинаций характеризуется расстоянием между ними в смысле Хэмминга, называемым кодовым расстоянием. Оно выражается числом элементов, в которых комбинации отличаются одна от другой, и обозначается через d. Минимальное количество элементов, в которых все комбинации кода отличаются друг от друга, называется минимальным кодовым расстоянием d0. Минимальное кодовое расстояние – параметр, определяющий помехоустойчивость избыточного кода. В общем случае для обнаружения всех ошибок до
-кратных включительно минимальное кодовое расстояние 
. (3)Минимальное кодовое расстояние, необходимое для одновременного обнаружения и исправления ошибок:
, (4)где t– число исправляемых ошибок.
Для кодов, только исправляющих ошибки:
(5)Соотношения (3), (4) и (5) определяют лишь кратность гарантийно обнаруживаемых и исправляемых ошибок. Обычно коды обнаруживают и исправляют часть ошибок и более высокой кратности.
К наиболее употребляемым избыточным кодам можно отнести блоковые и непрерывные коды.
Блоковые коды характеризуются тем, что исходная непрерывная информационная последовательность разделяется на отдельные части, каждая из которых кодируется отдельно и независимо от других частей, образуя раз решенные слова избыточного кода.
Равномерные блоковые коды характеризуются одинаковой длиной разрешенных кодовых слов, в отличие от неравномерных кодов.
В непрерывных кодах исходная информационная последовательность не разделяется на части, а кодируется непрерывно, причем избыточные элементы формируются на определенных позициях между информационными. Равномерные блоковые коды подразделяются на линейные и нелинейные.
Линейные коды образуют наиболее обширный подкласс кодов и определяются тем, что сумма по модулю для двух и более разрешенных комбинаций кода дает комбинацию этого же кода.
Нелинейные коды не обладают этим свойством. Примером нелинейных кодов является код с постоянным весом, применяемый в телеграфии. В некоторых случаях линейные коды называют групповыми, что обусловлено математическим описанием подмножества разрешенных кодовых слов длины nкак подгруппы в группе всех слов длины n. Линейный код, в котором информационные и проверочные элементы разделены и расположены на строго определенных позициях, называется систематическим, в отличие от несистематических кодов, в которых нельзя в явном виде выделить информационные и проверочные элементы. Систематические коды получили наибольшее распространение. Систематические коды, как правило, обозначаются (n, k) – кодами и включают: коды с проверкой на четность, коды Хэмминга, циклические коды, коды с повторением, итеративные коды, каскадные, коды Рида–Малера, дециклические коды и много других [3, 32].
В информационных системах для передачи коротких команд управления нашли наибольшее применение циклические коды; для обнаружения ошибок при встроенном контроле аппаратуры обработки – коды с одной проверкой на четность; при хранении информации – коды с повторением; при непрерывной передаче больших массивов измерительных данных – сверточные коды. Для повышения эффективности обработки избыточных кодов развиваются различные квазиоптимальные методы декодирования, использующие дополнительную информацию о ненадежных элементах передаваемых данных.
3. Циклические коды
3.1 Задание циклических кодов
Наиболее распространенным подклассом линейных кодов являются циклические коды. Это обусловлено относительно простым построением кодера и декодера, обнаруживающего ошибки, при достаточно высоких корректирующих способностях кода. Эти коды позволяют преодолеть некоторые трудности, связанные с технической реализацией, свойственные линейным кодам. В информационной системе циклические коды предпочтительны для передачи сообщений небольшой длины, например, команд управления объектами.
Алгебраическая структура циклических кодов впервые была исследована Боузом, Чоудхури и Хоквингемом, поэтому они известны как БЧХ-коды. Эти коды характеризуются следующими свойствами [7, 110]: длиной кодовых последовательностей
(6)где т = 1,2,3,…;
числом проверочных элементов, не превышающим величины
, т.е. 
(7)способностью обнаруживать все пакеты ошибок длины
(8)циклическим сдвигом разрешенной комбинации кода, приводящим к образованию разрешенной комбинации; этого же кода.
Возможно задание циклических БЧХ-кодов при помощи порождающих или проверочных матриц аналогично общим правилам, построения линейных кодов. Однако воспользуемся более простыми инженерными методиками, базирующимися на алгебраических понятиях. В этом случае более удобной является запись кодовых комбинаций в виде полинома переменной х:
Коэффициенты aiпредставляют собой цифры данной системы счисления. В двоичной системе счисления коэффициенты могут принимать одно из двух значений 0 или 1. Так, двоичное четырехразрядное число 1001 может быть записано в виде полинома
Это выражение устанавливает однозначное соответствие между двумя формами записи кодовых комбинаций.
Циклические коды образуются умножением каждой комбинации – элементного безызбыточного кода, выраженной в виде многочлена G (х), на образующий полином Р (х) степени (п – k). При этом умножение производится по обычным правилам с приведением подобных членов по модулю два [6, 98]. Следовательно, в случае отсутствия ошибок любая разрешенная кодовая комбинация циклического кода должна разделиться на образующий полином Р (х) без остатка. Появление остатка от деления указывает на наличие ошибок в кодовой комбинации. При этом гарантийно обнаруживаются ошибки, определяемые выражениями (7) и (8).
Кроме того, обнаруживается большая часты
ошибок более высокой кратности.Широкое применение нашел другой метод, который в отношении степени избыточности и помехоустойчивости приводит к построению эквивалентного циклического кода. В соответствии с этим методом каждая кодовая комбинация первичного кода G (х) умножается на одночлен Xn - k. Это эквивалентно приписыванию справа к комбинации G (х), записанной в двоичной форме, (п – k) нулей. Произведение G(х) xn - kделится на образующий полином Р (х) степени (п – k):
(9)где Q (х) – частное от деления такой же степени, как и G(х); R (х) – остаток.
Так как частное Q (х) имеет такую же степень, как и кодовая комбинация G (х), то, следовательно, Q (х) является кодовой комбинацией этого же простого k-элементного кода.
Умножая обе части равенства на Р (х) получим: