GROUP (вторая лаба), страница 2

Таблица 2.2 Таблица 2.3

Код, исправляющий двойные Код, исправляющий пачки в

независимые ошибки два и менее символов

n разряда Опознаватель n разряда Опознаватель

1 0000001 1 00001

2 0000010 2 00010

3 0000100 3 00100

4 0001000 4 01000

5 0001111 5 01101

6 0010000 6 00111

7 0100000 7 01110

8 0110011 8 10000

9 1000000 9 10000

Таблица 2.4

Код, исправляющий пачки в

три и менее символов

n разряда Опознаватель

1 0000001

2 0000010

3 0000100

4 0001000

5 0010000

6 0100000

7 0001001

8 0010010

9 0100100

10 1000000

Определение проверочных равенств

Пользуясь таблицей опознавателей одиночных ошибок в каж-

дом из разрядов, нетрудно определить, символы каких разрядов

должны входить в каждую из проверок на четность.

Возьмем в качестве примера табл. 2.1 опознавателей для

кодов, предназначенных исправлять одиночные ошибки.

В принципе можно построить код, усекая эту таблицу на лю-

бом уровне. Однако оптимальными будут коды, которые среди ко-

дов, имеющих одно и то же число проверочных символов, допуска-

ют наибольшее число информационных символов, например, код

(7,4)

n=7, к=4.

Усечем эту таблицу на 7-м разряде и найдем номера разря-

дов, символы которых должны войти в каждое из проверочных ра-

венств.

Предположим, что в результате первой проверки на четность

для младшего разряда опознавателя будет получена единица. Оче-

видно, это может быть следствием ошибки в одном из разрядов,

опознаватели которых в младшем разряде имеют единицу.

Следовательно, первое проверочное равенство должно включать

символы 1-го, 3-го, 5-го и 7-го разрядов

а 41  0+ 4  0а 43  0+ 4  0а 45 0 + а 47 0 = 0.

Единица во втором разряде опознавателя может быть следс-

твием ошибки в разрядах, опознаватели которых имеют единицу во

втором разряде. Отсюда, второе проверочное равенство должно

иметь вид

а 42 0 + а 43 0 + а 46 0 + а 47 0 =0.

Аналогично находим и третье равенство

а 44 0 + а 45 0 + а 46 0 + а 47 0 =0.

Чтобы эти равенства при отсутствии ошибок удовлетворялись

при любых значениях информационных символов в кодовой комбина-

ции, в нашем распоряжении имеется три проверочных разряда. Мы

должны так выбрать номера этих разрядов, чтобы каждый из них

входил только в одно из равенств. Это обеспечит однозначное

определение значений символов в проверочных разрядах при коди-

ровании. Указанному условию удовлетворяют разряды, опознавате-

ли которых имеют по одной единице. В нашем случае это будут

первый, второй и четвертый разряды.

Таким образом, для кода (7,4), исправляющего одиночные

ошибки, искомые правила построения кода, т.е. соотношения, ре-

ализуемые в процессе кодирования, принимают вид

а 41 0= а 43 0 + а 45 0 + а 47 0 ;

а 42 0= а 43 0 + а 46 0 + а 47 0 ;

а 44 0= а 45 0 + а 46 0 + а 47 0 .

Введение проверочного разряда, обеспечивающего четность

числа единиц во всей кодовой комбинации, а 48 0= а 4i 0мод 42 0 позволяет

построить код (8,4), способный одновременно исправлять единич-

ные ошибки и обнаруживать двойные.

Используя таблицу опознавателей (табл.2.2) и рассуждая

аналогичным образом, можно составить проверочные равенства для

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

ошибки. Например, для кода (8,2), получающегося усечением этой

таблицы на 8-м разряде, найдем следующие соотношения, которые

необходимо реализовать в процессе декодирования и кодирования

а 41 0 + а 45 0 + а 48 0= 0 а 41 0= а 45 0 + а 48

а 42 0 + а 45 0 + а 48 0= 0 а 42 0= а 45 0 + а 48

а 43 0 + а 45 0= 0 а 43 0= а 45

а 44 0 + а 45 0= 0 а 44 0= а 45

а 46 0 + а 48 0= 0 а 46 0= а 48

а 47 0 + а 48 0= 0 а 47 0= а 48 0.

Мажоритарное декодирование групповых кодов

Мажоритарное декодирование базируется на системе провероч-

ных равенств. Система последовательно должна быть разрешена от-

носительно каждой из независимых переменных, причем в силу из-

быточности это можно сделать не единственным способом.

Любой символ а 4i 0 выражается d различными независимыми спо-

собами через комбинации других символов. При этом может исполь-

зоваться тривиальная проверка а 4i 0=a 4i 0. Результаты вычислений по-

даются на соответствующий этому символу мажоритарный элемент.

Последний представляет собой схему, имеющую d входов и один вы-

ход, на котором появляется единица, когда возбуждается больше

половины входов. Если ошибки отсутствуют, то проверочные равен-

ства не нарушаются и на выходе мажоритарного элемента получаем

истинное значение символа. Если число проверок d > 2s+1 , то

появление ошибки кратности s и менее приводит к нарушению не бо-

лее s проверок. Поэтому правильное решение может быть принято

по большинству неискаженных проверок. Чтобы указанное условие

выполнялось, любой другой символ (не проверяемый) должен входить

не более, чем в одно проверочное равенство. В этом случае мы

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

Построим системы разделенных проверок для декодирования ин-

формационных символов рассмотренного ранее группового кода

(8,2). Поскольку код рассчитан на исправление любых двойных

ошибок, число проверочных равенств для определения каждого сим-

вола должно быть не менее 5. Подставив в равенства 1 и 2 значе-

ния а 48 0, полученные из равенства 5 и 6, и записав их относитель-

но а 45 0, совместно с равенствами 3 и 4 и тривиальным равенством

а 45 0=а 45 0 получим систему разделенных проверок для символа а 45 0. Ана-

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

а 45 0= а 46 0 + а 41 0 а 48 0= а 43 0 + а 41

а 45 0= а 47 0 + а 42 0 а 48 0= а 44 0 + а 42

а 45 0= а 43 0 а 48 0= а 46

а 45 0= а 44 0 а 48 0= а 47

а 45 0= а 45 0 а 48 0= а 48 0.

Описание программного обеспечения

При запуске программы появляется два окна с меню. В одном

окне - этапы выполнения программы, в другом обозначение кодов.

Сначала выбираем код.

Первый этап выполнения - составление уравнений. Для состав-

ления уравнений декодирования необходимо, пользуясь таблицей,

последовательно, без пробелов ввести номера разрядов. Для сос-

тавления уравнения кодирования ввести номера проверочных разря-