10.6. Другой метод исправления ошибок

Метод исправления ошибок, описываемый в этом разделе, не сильно отличается от метода, разобранного в предыдущем разделе, однако в некоторых случаях он приводит к более простым схемам. Этот метод годится для любого кода, порождающий многочлен которого может быть разложен из два множителя, степень каждого из которых по крайней мере не меньше длины любой исправимой пачки ошибок. Для простоты изложения все рассуждения здесь будут проводиться только для кодов Файра.

Предположим, что передавался вектор и появилась пачка ошибок Тогда полученный вектор равен . В этом случае проверочные вычисления состоят в делении многочлена отдельно на и на Для кодового вектора оба остатка будут равны нулю, а если они не равны нулю, то в них содержится информация относительно появившихся ошибок. В последнем случае, поскольку кодовый вектор, и, следовательно, делится и на и на остатки от деления

(кликните для просмотра скана)

будут совпадать с остатками от деления многочлена соответственно на и на Пусть

где степень многочлена меньше степени многочлена а степень многочлена меньше с.

Исправление ошибок можно производить следующим способом.

1. Умножить (X) на и привести результат по модулю т. е. разделить его на и взять остаток. Умножить на X и привести результат по модулю многочлена

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

3. Если полученные многочлены когда-либо окажутся равными многочленами степени, меньшей чем то оба они будут равны и первый шаг был повторен раз. Таким образом, комбинация ошибок место, с которого она начинается, найдены и место, с которого она начинается, найдены и ошибки можно исправить, вычитая вектор из полученного вектора.

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

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

Вычисление проверочных символов можно производить, используя два регистра сдвига (один для а второй для типа, описанного в разд. 8.5, изменяя их таким образом, чтобы в них производилось автоматическое умножение входа на В этих устройствах сдвиг с нулевым входом эквивалентен умножению на X и приведению результата по модулю соответственно или Схема, изображенная на рис. 10.5, приспособлена специально для кода Файра, рассматриваемого в примере на стр. 217. Ее работу можно описать следующим образом:

1. Полученный вектор одновременно вводится в буферное запоминающее устройство и в оба регистра сдвига, причем в обоих регистрах производится сдвиг после каждого поступления на вход символа полученного вектора. (Клапан 2 открыт, клапан 1 закрыт.)

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

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

3. Если содержимое разрядов обоих регистров сдвига в какой-либо момент совпадает, то это значит, что оба они содержат комбинацию ошибок и ошибки произошли в следующих b символах, которые должны появиться из буферного запоминающего устройства, Теперь клапан 1 должен быть открыт, а клапан 2 закрыт. После того, как из буферного запоминающего устройства снова начнут поступать символы, должны производиться сдвиги регистров после появления каждого символа, в результате чего комбинация ошибок будет вычитаться из полученного вектора.

Рис. 10.5. Схема для исправления ошибок в коде Файра.

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

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

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

Если нужен код, длина которого меньше естественной длины кода Файра, то некоторые информационные символы высших порядков могут быть заменены нулями и отброшены. Это не повлияет на процесс кодирования. На процесс исправления ошибок это повлияет снова тем же самым образом, как это было описано в предыдущем разделе, и изменения могут быть внесены в основном аналогичными методами. Имеется, однако, одно упрощение. Любое число сдвигов, кратное числу не влияет на содержимое регистра сдвига, соответствующего многочлену Далее, любое число сдвигов, кратное с, не влияет на содержимое регистра сдвига, соответствующее многочлену и любое число сдвигов в регистре, соответствующем может быть осуществлено просто сдвигом входного контакта регистра.

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

Код получается в результате сокращения кода Файра, естественная длина которого порожденного многочленом

1. Код получается отбрасыванием 65 информационных символов. На рис. 10.5. показана схема второго типа для исправления ошибок кодом полной длины. Ее необходимо изменить, введя операции, эквивалентные 65 дополнительным сдвигам в общих регистрах, или, другими словами, умножению входа каждого регистра сдвига на

Рис. 10.6. Схема для исправления ошибок для укороченного кода Файра.

Так как в схеме, показанной на рис. 10.5, вход всегда умножается на то теперь вход должен умножаться на В регистре, соответствующем многочлену любое число сдвигов, кратное 9, не меняет содержимого регистра, так что 70 сдвигов эквивалентны сдвигам. В свою очередь 7 дополнительных сдвигов эквивалентны соединению входа с восьмым разрядом регистра сдвига. В регистре, соответствующем многочлену любое число сдвигов, кратное 31, не меняет содержимого регистра, и, следовательно, умножение на эквивалентно умножению на Вычет по модулю равен так что во втором регистре умножение на эквивалентно умножению на

1. Его можно осуществить, соединяя вход с первым, третьим и четвертым разрядами этого регистра, как это показано на рис. 10.6.

В других отношениях схема остается прежней и работает в точности так же, как это показано на рис. 10.5.

Схемы, изображенные на рис. 10.4 и на рис. 10.6, приводят в точности к одинаковым конечным результатам для любого входного вектора. В рассматриваемом частном случае для схемы, показанной на рис. 10.6, требуется меньше элементов. Аналогично схемы, изображенные на рис. 10,3 и на рис. 10.5, эквивалентны, однако для схемы типа 10.3 требуется меньше элементов.