Построение группового корректирующегоий кода объёмом 9 слов (48121)

Посмотреть архив целиком










Индивидуальное задание по Теории информации


Подготовил В.С. Прохоров



Построить групповой корректирующий код объёмом 9 слов. Код должен обеспечивать исправление одиночных и обнаружение двойных ошибок.

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

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


,


где Q – требуемый объём кода. В нашем случае Q=9, поэтому



Отсюда получаем .



Далее находим число n из неравенства



Подставляем и подбором находим минимальное n, удовлетворяющее неравенству. В нашем случае

.



Далее мы должны составить таблицу опознавателей. Для этого необходимо ввести понятие вектора ошибок и опознавателя. Вектор ошибок это n-разрядная двоичная последовательность, имеющая единицы во всех разрядах, подвергшихся искажению, и нули в остальных разрядах. (Пример: искажению подверглись два младших разряда 6-разрядного сообщения - тогда вектор ошибки будет выглядеть как 000011), а опознаватель – некоторая сопоставленная этому вектору контрольная последовательность символов. В нашем случае векторы ошибок имеют разрядность 7 бит, так как , опознаватели имеют разрядность 3 бит, так как . Опознаватели рекомендуется записывать в порядке возрастания (нулевую комбинацию не используем).



Векторы ошибок

Опознаватели

1

0000001

001

2

0000010

010

3

0000100

011

4

0001000

100

5

0010000

101

6

0100000

110

7

1000000

111


Теперь необходимо определить проверочные равенства и сформулировать правила построения кода, способного исправлять все одиночные ошибки.

Выбираем из таблицы строки, где опознаватели имеют в первом (младшем) разряде единицу. Это строки 1, 3, 5 и 7. Тогда первое проверочное равенство будет выглядеть так:



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

Это строки 2, 3, 6, 7.

Тогда второе проверочное правило выглядит так:



И, наконец выбираем строки, где опознаватели имеют единицу в третьем разряде. Это строки 4, 5, 6, 7. Следовательно третье проверочное равенство выглядит так:



Далее нужно отобрать строки, где опознаватели имеют всего одну единицу. В нашем случае это строки 1, 2 и 4. Возвращаемся к полученным ранее уравнениям. В левой части оставляем члены с выбранными нами только что индексами, а остальные переносим в правую часть:



Эти три уравнения и называются правилами построения кода. Код, построенный по этим правилам, может исправить все одиночные ошибки. Но нам необходимо, чтобы код также мог обнаруживать двойные ошибки. Для этого добавим к трём уравнениям, полученным ранее, ещё одно:



Мы получили окончательные правила построения кода, способного исправлять все одиночные и обнаруживать двойные ошибки:

Используя правила построения корректирующего кода (*), построим таблицу разрешённых комбинаций группового кода объёмом 9 слов, способного исправлять все одиночные и обнаруживать двойные ошибки. В колонку «безызбыточный код» записываем девять (по заданию Q=9) комбинаций по возрастанию (нулевую комбинацию не используем).




(*)


Все колонки, кроме , , и , содержимое которых определяется формулами (*), заполняем цифрами из безызбыточного кода:


слово

безызбыточный код

код

0001


0

0

0


1



0010


0

0

1


0



0011


0

0

1


1



0100


0

1

0


0



0101


0

1

0


1



0110


0

1

1


0



0111


0

1

1


1



1000


1

0

0


0



1001


1

0

0


1




Чтобы заполнить колонки , , и , подставляем значения необходимых переменных в соответствующие уравнения из (*). Например, для строки 9 (слово ) получаем следующее:



слово

безызбыточный код

избыточный код

0001

1

0

0

0

0

1

1

1

0010

1

0

0

1

1

0

0

1

0011

0

0

0

1

1

1

1

0

0100

1

0

1

0

1

0

1

0

0101

0

0

1

0

1

1

0

1

0110

0

0

1

1

0

0

1

1

0111

1

0

1

1

0

1

0

0

1000

0

1

0

0

1

0

1

1

1001

1

1

0

0

1

1

0

0



Случайные файлы

Файл
176449.rtf
168429.rtf
2416-1.rtf
114896.rtf
90296.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.