Дополнительная информация по коду фирмы IBM

Многочлен ошибки в этом случае имеет вид:

E(x) = x je(x),

где x j – адрес ошибки, (х) определяется по результатам проверок строк на нечетность. Номер дорожки с искаженными символами может быть найден, исходя из следующего.

Пусть F1(x) = 0 ... Fl(x) = 0; Rl(x) = 0 и при считывании на дорожке с n возникла пачка ошибок. В результате декодирования получим некоторый многочлен

код фирмы IBM
или
код фирмы IBM ,

где k – число дорожек, на которое отстоит дорожка с известным номером n от дорожки, где возникла пачка ошибок j.

Если пачка ошибок возникла только по одной дорожке, то, умножив R'(x) на xk с приведением по модулю g(x), получим R"(x).

Поэтому при декодировании одновременно с вычислением R'(x) осуществляется вычисление R"(x). Для определения номера дорожки с искаженными символами производится последовательное домножение R'(x) на х; х2; ...; хn –1.

На каждом шаге, начиная с R'(x), результат приводится по модулю g(x) и затем сравнивается с R"(x).

Процесс прекращается, как только на каком-либо i-м шаге зафиксировано равенство (в этом случае k = i – 1 и известная величина n определяет номер искомой дорожки) или после проведения n сравнений. В последнем случае фиксируется наличие неисправимой ошибки.

Требования к образующему многочлену g(x).

У произвольного g(x) степени n остаток Rl(x) может иметь как четное, так и нечетное количество единиц. Такая нечеткость не позволяет проверкой по строке при считывании считать, содержит Rl(x) ошибку или нет. Следовательно, необходимо выбрать такой g(x), который обеспечит детерминированность Rl(x) по числу членов.

Рассмотрим с этой целью полную сумму S(x), образовывающуюся при кодировании многочленов всех строк:

код фирмы IBM.

Поскольку каждый Fi(x) состоит из нечетного числа членов (дополнен до нечетности), а умножение F(x) на х в любой степени числа членов в нем не меняет, сумма будет содержать четное число членов, если l – четно (что при записи на МЛ обычно соблюдается).

Можно представить, что

код фирмы IBM .

Выберем g(x) с четным числом членов

код фирмы IBM ,

тогда


или

и Rl(x) – всегда четно независимо от Fi(x).

Сделаем многочлен R'l(x) = Rl(x) g'(x) – нечетным, т.к. g'(x) – не четно и запишем его в конец кадра.

Пример

код фирмы IBM ;
код фирмы IBM

т.е. g(x) – четно, а g'(x) = g(x) / (x 1) – нечетно!

Выбор g'(x) в качестве поправки к Re(x) не случаен.

В результате декодирования получаем:

код фирмы IBM.

Можно показать, что только при введении в качестве поправки g'(x), справедливо равенство:

код фирмы IBM.

Так как

код фирмы IBM

В таблице 8.2 приведены некоторые образующие многочлены g(x) и соответсвующие им g'(x) для разных n – количеств дорожек:

Таблица 8.2

№ п/п Степень Многочлен Двоичная последовательность
1 1 x 1 11
2 2 x2 x 1 111
3 3 x3 x 1 1011
4 x3 x2 1 1101
5 4 x4 x 1 10011
6 x4 x3 1 11001
7 x4 x3 x2 x 1 11111
8 5 x5 x2 1 100101
9 x5 x3 1 101001
10 x5 x3 x 2 x 1 101111
11 x5 x4 x 2 x 1 110111
12 x5 x4 x 3 x 1 111011
13 x5 x4 x 3 x2 1 111101
14 6 x6 x 1 1000011
15 x6 x3 1 1001001
16 x6 x4 x 2 x 1 1010111
17 x6 x4 x 3 x 1 1011011
18 x6 x5 1 1100001
19 x6 x5 x 2 x 1 1100111
20 x6 x5 x 3 x2 1 1101101
21 x6 x5 x 4 x 1 1110011
22 x6 x5 x 4 x2 1 1110101
23 7 x7 x 1 10000011
24 x6 x3 1 10001001
25 x7 x3 x 2 x 1 10001111
26 x7 x4 1 10010001
27 x7 x4 x 3 x2 1 10011101
28 x7 x5 x 2 x 1 10100111
29 x7 x5 x 3 x 1 10101011
30 x7 x5 x 4 x3 1 10111001
31 x7 x5 x 4 x3 x2 x 1 10111111
32 x7 x6 1 11000001
33 x7 x6 x 3 x 1 11001011
34 x7 x6 x 4 x 1 11010011
35 x7 x6 x 4 x2 1 11010101
36 x7 x6 x 5 x2 1 11100101
37 x7 x6 x 5 x3 x2 x 1 11101111
38 x7 x6 x 5 x4 1 11110001
39 x7 x6 x 5 x4 x2 x 1 11110111
40 x7 x6 x 5 x4 x3 x2 1 11111101
41 8 x8 x4 x 3 x 1 100011011
42 x8 x4 x 3 x2 1 100011101
43 x8 x5 x 3 x 1 100101011
44 x8 x5 x 3 x2 1 100101101
45 x8 x5 x 4 x3 1 100111001
46 x8 x5 x 4 x3 x2 x 1 100111111
47 x8 x6 x 3 x2 1 101001101
48 x8 x6 x 4 x3 x2 x 1 101011111
49 x8 x6 x 5 x 1 101100011
50 x8 x6 x 5 x2 1 101100101
51 x8 x6 x 5 x3 1 101101001
52 x8 x6 x 5 x4 1 101110001
53 x8 x6 x 5 x4 x2 x 1 101110111
54 x8 x6 x 5 x4 x3 x 1 101111011
55 x8 x7 x 2 x 1 110000111
56 x8 x7 x 3 x 1 110001011
57 x8 x7 x 3 x2 1 110001101
58 x8 x7 x 4 x3 x2 x 1 110011111
59 x8 x7 x 5 x 1 110100011
60 x8 x7 x 5 x3 1 110101001
61 x8 x7 x 5 x4 1 110110001
62 x8 x7 x 5 x4 x3 x2 1 110111101
63 x8 x7 x 6 x 1 111000011
64 x8 x7 x 6 x3 x2 1 111001111
65 x8 x7 x 6 x4 x2 x 1 111010111
66 x8 x7 x 6 x4 x3 x2 1 111011101
67 x8 x7 x 6 x5 x2 x 1 111100111
68 x8 x7 x 6 x5 x4 x 1 111110011
69 x8 x7 x 6 x5 x4 x2 1 111110101
70 x8 x7 x 6 x5 x4 x3 1 111111001

Данный код способен исправлять все пачки ошибок, возникающие по одной дорожке, за исключением пачек вида:

,

где z(x) – произвольно.

Пример

Пусть на запись 10 дорожечную МЛ по первым 9-ти дорожкам поступают следующие информационные символы:

код фирмы IBM
Рис. 8.7

Из таблицы выбираем:

;

11000110011;

Получаем остаток для записи на МЛ по седьмой строке.

код фирмы IBM
Рис. 8.8

Запишем в 7-ую дорожку нечетное число единиц. Предположим, что при считовании исказились символы по 7 дорожке (голубой фон).

При декодировании необходимо вычислить многочлены:

код фирмы IBM.

Вычислим L(x) так же как и .

код фирмы IBM
код фирмы IBM
Рис. 8.9

Найдем R"(x). При каждом обнаружении ошибки проверкой по строке одновременно со сдвигом к n-ному (десятому) разряду присуммируется "1". При этом происходит доумножение на x и приведение по mod g(x).

код фирмы IBM.

Ищем последовательность на каждом шаге.

код фирмы IBM
Рис. 8.10

Ост.7 = R"(x) = 1100001110.

Займемся сравнением L(x) с R"(x) при сдвиге L(x) и приведением по mod g(x).

код фирмы IBM

Технические средства реализации специального двухстепенного итеративного кода

Кодирование

код фирмы IBM
Рис. 8.11. Блок схема кодирующего устройства

Очередность выполнения операций обеспечивается схемой управления (не показана).

Схема кодирующего регистра: для n = 10 и

код фирмы IBM .
код фирмы IBM
Рис. 8.12

Регистр 3 осуществляет параллельное и поразрядное суммирование строк по модулю 2 с одновременным доминированием Ri(x) над x и делением результата на g(x).

Прибавление сводится к инверсированию содержимого 1; 5 и 10 разрядов.

Декодирование

код фирмы IBM
Рис. 8.13. Блок схема декодирующего устройства (без повторного протягивания ленты)

Сигналы c МЛ, включая n-ую, через усилители 1 поступают на входной регистр 2. С выхода 2 параллельно сигналы поступают:

  • В схему 3 свертки по mod 2 для определения сигнала ошибки по строке с последующей записью в регистр 4.
  • В схему декодирующего регистра 5, где по результатам обработки всего кадра определяются многочлен R*(x) с последующим суммированием по модулю 2 g'(x). http://peredacha-informacii.ru/
  • Каждый сигнал, свидетельствующий о нарушении нечетности по строке, поступает в схему декодирующего регистра 6, где по результатам обработки всего кадра определяется контрольный многочлен исходя из предположения, что все ошибки произошли на дорожке с номером n!

Декодирующий регистр 5 аналогичен кодирующему.

Декодирующий регистр 6 для n = 10 и код фирмы IBM.

код фирмы IBM
Рис. 8.14

При каждом обнаружении ошибок проверкой по строке одновременно со сдвигом информации в регистре к его n-ному (десятому) разряду присуммируется "1". При этом в регистре происходит домножение на х с приведением результат по mod g(x).

Если содержимое регистра 5 не нуль, что свидетельствует об обнаружении ошибки, то схемой 7 производится сравнение "на равно" содержимого регистров 5 и 6 с последующим сдвигом содержимого регистра 5.

Операция сравнение повторяются до тех пор, пока сравнение "на равно" не выполнится, либо пока операция не повторится n раз.

При выполнении сравнения циклический счетчик 8 фиксирует номер дорожки с искаженной информацией и на один из входов логической схемы "и" 7, соответствующей этой дорожке, поступает сигнал управления. После этого весь кадр индикации построчно выводится из буферного З.У. 10 через сумматоры по mod 2 на выходной регистр 11.

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