Построение группового корректирующегоий кода объёмом 9 слов (стр. 1 из 2)
Индивидуальное задание по Теории информации
Подготовил В.С. Прохоров
Построить групповой корректирующий код объёмом 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 |
Перейдём к построению функциональной схемыкодирующего устройства (см. соответствующий рисунок ниже). Назначение кодирующего устройства – внесение избыточности в код по заданным нами правилам. Схему строим на основании равенств (*). На схеме используется логический элемент «сумматор по модулю два», обозначенный М2. На схеме имеются два регистра, построенные на D-триггерах. Один из них содержит безызбыточный код и имеет разрядность 4 бит, так как
, а другой содержит избыточный код и имеет разрядность 8 бит, так как 
. Принцип работы схемы таков: по сигналу синхронизации на k-разрядный регистр поступает кодовая комбинация, подлежащая кодированию. Затем с помощью сумматоров эта комбинация кодируется (вносится избыточность). Сумматор С1 реализует первое равенство из (*), сумматор С2 – второе, С3 – третье, а С4 – четвёртое. И, наконец, по сигналу синхронизации полученный избыточный код записывается в 8-разрядный регистр. Далее начинается кодирование следующей комбинации.