184 гл. е. схемная реализация

имеем

S5 (х) = X* + X» + х« + л: + л:2 -fx,

Se (х) = х" + X» -f х -f х" -f х» -f х.

Следовательно, если ошибка содержится в пятой или шестой позициях, то синдром соответственно равен (01100110110) или (00110011011) Наличие двух дополнительных ошибок в И старших разрядах приводит к тому, что в соответствующих позициях два из этих битов заменяются на противоположные.

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

ЗАДАЧИ

6.1. а. Построить поле GF (8) с помощью примитивного многочлена р{х)- = з-\- х-\- I (а обозначает примитивный элемент а = х).

б. Для заданного произвольного многочлена g (х) над GF (2) построить простое логическое устройство, вычисляющее g (а*).

в. Сконструировать устройство, реализующее умножение двух произвольных элементов поля GF (8).

г. Сконструировать устройство, реализующее умножение произвольного элемента поля GF (8) на скаляр а*.

д. Указать те элементы поля GF (8), квадраты которых также принадлежат этому полю; затабулировать такие элементы.

е. Сконструировать устройство, вычисляющее квадратный корень из тех элементов поля GF (8), для которых он существует,

6.2. Пусть поле Gf (16) задано многочленом х-\-х+ 1. Определим два произвольных элемента этого поля:

V = Уз + Va + yix + Vo. где коэффициенты принадлежат полю GF (2). Построить параллельное логическое устройство, выполняющее умножение двух произвольных элементов из

6.3. Исходя из равенств р- = if"~-f и 2" - I = 5]"=о2 "

пользуя устройство возведения в квадрат и умножитель, сконструировать итеративное логическое устройство вычисления элемента по заданному р за m тактов работы.

6.4. Циклический (15, 9, 5)-код над GF (4) порождается многочленом

g (х) = xo-i-Зх +х+ 2х+2х+ 1.

а. Построить кодирующее устройство для этого кода, основанное на регистре сдвига.

б. Построить декодер Меггитта для этого кода.

6.5. Порождаемый многочленом g (х) = х? х-{- 1 двоичный циклический код позволяет исправлять пакеты ошибок длины 2,

а. Чему равны длина и скорость этого код,а?

зАдАчИ 186

б. Найти минимальное расстояние этого кода.

в. Сконструировать систематический кодер для этого кода.

г. Сконструировать декодер с вылавливанием ошибок, позволяющий исправлять все пакеты длины 2.

6.6. Исправляющий три ошибки (23, 12)-код является циклическим с порождающим многочленом

g{x) = х+ xo-i- xo-i- + х*+I

(х) = х+ х»+ х-Ь хе -i- х + х + 1.

а. Найти проверочный многочлен h (х) этого кода.

б. Сконструировать кодер, использующий регистр сдвига.

в. Можно ли методом вылавливания ошибок исправлять все тройные ошибки? Почему?

6.7. Используя регистры сдвига с 4-битовыми регистрами, сконструировать кодер и декодер для рассмотренного в § 3.4 (17, 15)-кода Хэмминга над полем из 16 элементов. Показать все логические цепи.

6.8. В процессе считывания и записи в запомиианЗщем устройстве ЭВМ, состоящем из 256 8-битовых слов, возможны искажения одного 8-битового слова. Для борьбы с этим явлением решено воспользоваться укороченным кодом Хэмминга над GF (2*), исправляющим одно искаженное слово.

Описать (256, 252)-код и сконструировать кодер и декодер с вылавливанием ошибки. (Заметим, что задачей схемы является отыскание и исправление в памяти одного искаженного слова.)

6.9. Сконструировать кодер и декодер с вылавливанием ошибок для двоичного (19537, 19408)-кода Файра с порождающим многочленом g (х) = (х - 1) X X р (х), где р (х) - примитивный многочлен степени 10.

6.10. Задаваемый одним корнем в точке а поля GF (256) двоичный циклический код длины 17 представляет собой (17, 9, 5)-код, принадлежащий к классу квадратично-вычетных кодов. Найти порождающий многочлен кода и сконструировать модифицированный декодер с вылавливанием ошибок, позволяющий исправлять все двойные ошибки. Сконструировать также декодер, основанный иа просмотре таблицы синдромов. Сравнить сложность и скорость этих двух декодеров.

6.11. (7, 5)-код Рида-Соломона над GF (8) порождается многочленом g (х) = л: -f ах -f а*. Построить циклический код, исправляющий пакеты ошибок длины 2 над GF (8), выполняя следующую последовательность шагов.

а. Выписать порождающий многочлен исправляющего восьмеричные пакеты длины 2 кода, получающегося перемежением двух одинаковых исходных кодов Рида-Соломона.

б. Чему равны длина и скорость так построенного кода?

в. Составить дли этого кода схему кодера с использованием регистра

сдвига.

г. Сконструировать декодер с вылавливанием ошибок, позволяющий исправлять все пакеты длины 2.

6.12. Построить (1072, 1024)-код для исправления пакетов ошибок длины 16 путем укорочения и перемежения подходящего кода из табл. 5.1. Построить (1080, 1024)-код для исправления пакетов длины 20 путем укорочения и перемежения кода Файра.

6.13. Исправляющий две ошибки двоичный (31, 21)-код порождается многочленом

g (х) = Х + X» + + }fi + х + х + I.

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

ЗАМЕЧАНИЯ

Многие идеи данной главы уже ясно просматриваются как идеи теории дискретных фильтров, но с заменой поля вещественных или комплексных чисел на поле Галуа. Это смутно ощущалось еще в самом начале и становилось все более очевидным по мере развития предмета. Содержащие регистры сдвига устройства были сразу использованы большинством исследователей и вошли в литературу без всяких фанфар. Использование регистров сдвига в кодерах и декодерах можно найти в работах Питерсона [1960] и Ченя [1964]. В виде учебного материала эти идеи появились уже в книге Питерсона [1961]. Меггитт опубликовал описание устройств своих декодеров в 1960 и 1961 гг. Не совсем ясно, кому принадлежит идея декодера с вылавливанием ошибок, но обычно ее приписывают Прейнджу.

Способы модафикации декодера с вылавливанием ошибок, позволяющие корректировать исправляемые, но не вылавливаемые ошибки, рассматривал Касами 1964]. На методах Касами основан описанный в § 6.7 декодер для кода Голея. Использование отличных от циклических перестановок исследовала Мак-Вильямс [1964]. Другие ранние результаты приводятся в статьях Митчелла [1962] и Рудолфа и Митчелла [1964].

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

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