Р е ш е н и е. Вычислим хэммингово расстояние между всеми парами двоичных кодовых комбинаций:

Вычислим хэммингово расстояние между всеми парами двоичных кодовых комбинаций:

d₁₂=7; d₁₃=5;

d₂₃=6.

Вычислим минимальное кодовое расстояние:

d_min=min{7, 5, 6}=5.

В соответствии с формулой (2.1) вычислим кратность обнаруживаемых ошибок, приравняв левую и правую части этого неравенства:

d_min=R+1 5=R+1 R=4.

В соответствии с формулой (2.2) вычислим кратность исправляемых ошибок, приравняв левую и правую части:

d_min=2S+1 5=2S+1 S=2.

В соответствии с формулой (2.3) вычислим кратность обнаруживаемых и исправляемых ошибок, приравняв левую и правую части, с учетом ограничения (2.4):

d_min=R+S+1 5=R+S+1 R=3; S=1.

Ответ:

Исследуемый код может обнаружить ошибки кратности 4, либо исправить ошибки кратности 2, либо обнаружить ошибки кратности 3 и одну из них исправить.

2.4. Показатели качества корректирующего кода

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

либо

Отношение k/n называется нормой кода.

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

Оценим наибольшее возможное число Q (объем кода) разрешённых комбинаций n-значного двоичного кода, обладающего способностью исправлять взаимно независимые ошибки кратности S.

Общее число различных исправляемых ошибок для каждой разрешённой комбинации составляет Вместе с разрешенной комбинацией подмножество запрещенных комбинаций, представляющее эту разрешённую комбинацию, должно содержать:

комбинаций.

Так как эти подмножества не пересекаются, то объем кода можно рассчитать по формуле Хэмминга

(2.5)

2.5. Групповые коды

Коды, в которых все кодовые комбинации образуют группу, называются групповыми.

Алгебра изучает выполнение алгебраических операций над элементами некоторого множества М.

Алгебраические структуры характеризуются законами композиции и аксиомами, которым эти законы подчинены. Суть алгебраической операции – сопоставление паре x, у М элемента z М (это определение внутреннего закона композиции). Внешние законы композиции:паре x М и ω Ω сопоставляется элемент у М.

В группе действует один внутренний закон композиции. Обозначим в общем случае знак композиции символом «*».

Понятие группы вводится с помощью следующих аксиом:

(1) Замкнутость. Введённая операция «*» применяется к любым двум элементам группы, в результате получается третий элемент группы:

х, у М, х*у=z z М.

(2) Ассоциативный закон. Если х, у, z М, то х*(у*z)=(х*у)*z.

(3) Существует нейтральный элемент e такой, что х*е=х.

(4) Для каждого существует симметричный элемент (-x) такой, что x*(-x)=e.

Группа называется конечной, если множество её элементов конечно, и бесконечной – в противном случае. Количество элементов в конечной группе называется порядком группы.

Если операция, определенная в группе, коммутативна (то есть, для любых x, y M выполняется равенство x*y=y*x), то такая группа называется коммутативной или абелевой.

При построении помехоустойчивых кодов множество всех n-разрядных двоичных векторов образует абелеву группу порядка 2ⁿ относительно покомпонентного сложения по модулю 2. Нулевым элементом является n-разрядное двоичное кодовое слово 00…0. Относительно операции покомпонентного сложения по модулю 2 симметричным элементом для любого элемента х является сам элемент х, так как при поразрядном сложении по модулю 2 всегда х х=0.

В дальнейшем для образования кодов будем использовать группы векторов относительно операции поразрядного сложения по модулю 2.

Не всякое множество векторов образует группу относительно этой операции. Например, множество {011, 110, 111} не является группой, так как в нём нет нулевого элемента. Множество {000, 001, 110} не является группой, т. к. не выполняется аксиома замкнутости:

001 110=111 М.

Множество {000, 001, 110, 111} есть группа, так как

(1) Имеется нулевой элемент 000;

(2) Выполняется аксиома замкнутости:

001 110=111 M;

001 111=110 M;

110 111=001 M.

Подмножество Н группы М называется подгруппой группы М, если в нём удовлетворены аксиомы группы. Всякая подгруппа является группой относительно той операции, которая определена в группе.

Пусть в абелевой группе М задана подгруппа Н. Для простоты назовём операцию, относительно которой образована группа, сложением (обозначим его символом «+»).

Если x Н и x М, то множество элементов вида х+Н, получающихся при сложении элемента х с каждым элементом из Н, называется смежным классом группы М по подгруппе Н, порождаемым элементом х.

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

Беря последовательно элементы x_j М, не вошедшие в уже образованные смежные классы, можно разложить всю группу на смежные классы по подгруппе Н. Элементы x_j называются образующими.

Поиск по сайту: