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