Теория информации (стр. 17 из 29)

Рис.4. Устройство свертки по модулю q.

Устройство сравнения сравнивает r

и r *, в случае их несовпадения выносит решение о наличии ошибки в принятом слове. Схема на рис. 5 иллюстрирует принцип контроля суммирующего устройства.

Рис.5. Схема, иллюстрирующая принцип контроля суммирующего устройства.

Пусть в результате суммирования чисел N

и N получено N*. Остатки r и r также суммируются с выделением остатка r . Если остаток r *, полученный от деления числа N* на модуль q, не совпадает с r , то элемент сравнения сигнализирует о наличии ошибок в работе устройства.

Чаще всего используется q = 3, иногда выбирается q = 7. При увеличении значения q возрастает способность метода к обнаружению ошибок, но одновременно увеличивается объем контролирующего оборудования.

Рассмотрим пример применительно к схеме на рис. 5. Пусть q = 3, N

= 32 = 100000 , N = 29 = 011101 . Соответствующие этим числам остатки равны r = 2 = 10 , r = 2 = 10 (при q = 3 остатки могут принимать значения 0, 1, 2 и для их представления в двоичной форме достаточно двух контрольных разрядов). При отсутствии ошибок в работе устройства результат суммирования чисел N* = N + N = 61 = = 111101 , значение свертки по модулю 3 равно r * = 01 . Суммируя r и r и выделяя остаток по модулю 3, получаем r = 01 . Совпадение r * = r указывает на отсутствие ошибок. При наличии ошибок не имело бы места совпадение остатков r * и r .

Эффективность контроля по модулю характеризуется данными, приведенными в табл. 2.

Таблица 2

В таблице указано, какую часть всех возможных комбинаций ошибок составляют ошибки, которые не обнаруживаются при контроле по модулю. Как видно из приведенных данных, обнаруживаются все однократные ошибки; доля ошибок высокой кратности, оказывающихся необнаруженными, при модуле 7 меньше, чем при модуле 3. Тем самым эффективность контроля по модулю 7 выше, чем при модуле 3. Однако при контроле по модулю 7 контрольная часть слов содержит три двоичных разряда (вместо двух разрядов при модуле 3) и, кроме того, сложнее схемы формирования остатков (схемы свертки).

В заключение рассмотрим построение схем свертки по модулю 3. Общим для этих схем является следующий метод получения остатка. Каждый разряд числа вносит определенный вклад в формируемый остаток. В табл. 3 приведены остатки от деления на 3 значений, выражаемых единицами отдельных разрядов (т.е. весовых коэффициентов разрядов). Эти остатки для единиц нечетных разрядов равны 1, для четных разрядов они равны 2. Следовательно, для получения остатка от деления на 3 всего числа достаточно просуммировать остатки для единиц отдельных его разрядов и затем для получения суммы найти остаток от деления на 3.

Таблица 3

Например, пусть N = 11001011

; сумма остатков, создаваемых отдельными разрядами, S=1·2+1·1 + 0·2 + 0·1 + 1·2+0·1+1·2+1·1 = 8; далее, деля 8 на 3, получаем остаток r

= 2.

Схема свертки по модулю 3 для последовательной формы передачи чисел

Схема может быть выполнена в виде двухразрядного счетчика с циклом 3, построенного таким образом, что единицы нечетных разрядов поступающего на вход числа вызывают увеличение содержимого счетчика на единицу, а единицы четных разрядов вызывают увеличение числа в счетчике на два. Функционирование такого счетчика описывается табл. 4.

Здесь b— код, определяющий четность номера очередного разряда числа, поступающего на вход счетчика; примем для четных разрядов b = 0, для нечетных разрядов b = 1.

Таблица 4

Таблица 5

По этой таблице и таблице переходов JK-триггера (табл. 5) построены приведенные на рис. 6 карты, по которым находят логические выражения для входов триггеров ТТ1 и ТТ2 счетчика:

Рис.6. Карты, по которым находят логические выражения для входов триггеров ТТ1 и ТТ2 счетчика.

Представив выражения для J

и J

в базисе И-НЕ:

получим схему межтриггерных связей на рис.7. Логическая переменная b формируется триггером 3.

Этот триггер переключается тактовыми импульсами (ТИ), следующими с частотой поступления разрядов числа на вход счетчика. Таким образом, в моменты поступления нечетных разрядов триггер 3 устанавливается в состояние 1 и b = 1, в моменты поступления четных разрядов b= 0.

Рис.7. Схема межтриггерных связей.

Схема свертки для параллельной формы представления числа

При параллельной форме представления числа обычно используется пирамидальный способ построения схемы свертки, показанный на рис. 8.

Элементы А первого яруса формируют остатки для пар разрядов числа, выдавая уровень лог. 1 на один из выходов А

,А ,А в зависимости от значения остатка (0,1,2). В последующих ярусах используются однотипные элементы В, которые формируют остатки по результатам, выдаваемым парой элементов предыдущего яруса. На выходе элемента последнего яруса образуется остаток для всего числа.

Выходы элементов определяются следующими логическими выражениями: для первого яруса

для остальных ярусов

Если число разрядов n = 2

, то число ярусов в схеме свертки равно k, а число элементов составляет (n – 1).

4.4 Понятие качества корректирующего кода

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