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