Индивидуальное задание по Теории информации
Подготовил В.С. Прохоров
Построить групповой корректирующий код объёмом 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
Чтобы заполнить колонки , , и , подставляем значения необходимых переменных в соответствующие уравнения из (*). ............