У. Питерсон - Коды, исправляющие ошибки (1267328), страница 100
Текст из файла (страница 100)
Требование, состоящее в том, чтобы код дополнитель- ного числа был дополнением кодового числа, означает, что г" — 1 — (Ай+ В) =А(Ь вЂ” 1 — И)+ В. (!5.9) Это уравнение можно разрешить относительно В: !г" — 1 — А (Ь вЂ” !11 2 (15.10) Самодополняющийся код возможен тогда и только тогда, когда уравнение (15.10) удовлетворяется при пелом значении В. Расстояния АУ+ В-кода обладают теми же свойствами, что и расстояния соответствующего Ай-кода, так как (Ай, + В) — (А)Уз+ В) = АФ, — Айм )7рилер. Предположим, что требуется найти двоичный самодополняющийся А!у+В-код для кодирования десятичных знаков, исправляющий одиночные ошибки. Из табл. 15.1 видно, что наименьшее значение А, при котором существует АУ-код, удовлетворяющий условию М,(А,З) ~ 10, равно 19.
В этом коде наибольшее кодовое число будет равно по меньшей мере 19 Х 9 = 171, так что потребуется по меньшей мере п = 8 двоичных знаков. Из равенства (15.9) вытекает, что В = 42, и так как 19 Х 9+ 42 = 223 ( 2'„ то такой код возможен. В результате для кодирования десятичных знаков получается следующий код: Три других кода 235!+ 24, 25У+ 15 и 27У+ 6 также удовлетво- ряют основным требованиям для 8-значного двоичного кода [33). 15.7. Реализация Ай(- и Ай!+В-кодов При использовании вычислительных машин кодирование в случае АУ+ В-кода сводится к умножению подлежащего кодированию числа !т' на А и прибавлению к произведению числа В. с!тобы провести декодирование, можно просто вычесть В из полученного кодового числа и результат разделить на А.
Появление ненулевого остатка указывает на то, что произошла ошибка. Величина остатка 0 .00101010 1 00111101 2 01010000 3 01100011 4 01110110 5 10001001 6 10011100 7 10101111 8 11000010 9 11010101 характеризует величину ошибки, которая равна разности между полученным кодовым числом и тем кодовым числом, передача которого кажется наиболее правдоподобной. (См.
теорему 15.2 и задачу 15.1.) Обращение к таблице, в которой для каждого возможного остатка перечисляются соответствующие значения ошибок, является обычно наиболее удобным способом исправления ошибок прн работе вычислительной машины. Исправление ошибок А!у-кодом «без потерь», т. е. кодом, удовлетворяющим условиям теоремы 15.3, может быть проведено способом, аналогичным описанному в равд. 8.7 способу исправления ошибок для циклического кода Хэммннга. Первый шаг состоит в построении регистра, сдвиг которого эквивалентен умноженгпо на 2 по модулю А.
Такое устройство для А = 19 изображено па фиг. 15.1. Если в результате сдвига содержимое регясгра сдвига должно принять значение 19 нли больше, т. е. если содержимое регистра сдвига равно 10 или большему числу или равно 9, но па вход подана 1, то в момент сдвига из содержимого регистра сдвига необходимо вычесть 19. Вычитание числа 19 эквивалентно прибавлению числа 32 — 19 = 13 в 5-значном двоичном сумматоре.
Если в результате «проверки на наличие числа 1О или большего числа» на выходе логического устройства появилась 1, то в момент сдвига к содержимому регистра сдвига прибавляется число 13, или 01101 в двоичной записи. Этот регистр сдвига может быть использован для нахождения вычета числа по модулю 19. Для этого число в двоичной записи вводится в регистр, начиная со старших разрядов и кончая самым младшим разрядом.
Вычет совпадает с содержимым регистра сдвига. Исправление ошибок может быть завершено путем сдвигов регистра без подачи каких-либо данных на вход до тех пор, пока в регистре сдвига не появится + 1 или — 1 ( — ! появляется как 19 — ! = 18, илн в двоичной записи 10010). При этом нужно следить за числом требуемых сдвигов. Если ошибка появилась в 1-м разряде, то ее величина равна ~20 Так как 2 — примитивный элемент по модулю 19, то 2' = — 1, н, следовательно, если ошибка равна +2!, то — 1 появляется в регистре сдвига после 9 — ! сдвигов. Если ошибка равна — 2!, то после 9 — 1' сдвигов в регистре появляется +1.
Таким образом, положение ошибки может быть определено по числу сдвигов, а будет лн ошибка равна +2! нли — 2!, определяется тем, какое нз чисел +1 или — 1 появилось первым в регистре сдвига. Детальное построение схемы проводится так же, как в случае циклических кодов Хэммннга или циклических кодов, исправляющих пакеты ошибок, но с добавлением последовательных сумматоров для прибавления или вычитания поправки. Заметим также, что если в силу теоремы 15.5 ненулевое содержиМое регистра, представленного на фиг.
15.1, многократно сдви- Г Праеериа иа наличае числа!О ела болмаееа числа е Фиг. 1ВЛ. Регистр сдвига для умножения на 2 по модулю !9. гается при отсутствии символов на входе, то последовательно идущие символы малого порядка являются символами числа В = = (2" — 1)/А. 15.8. Разделниые сумматор и проверяющее устройство Часто требуется, чтобы кодовое слово поступало в проверочную систему с неизмененными информационными и проверочными символами, как это бывает в систематических линейных кодах. Если такая система используется для проверки сумматора, то также желательно, чтобы сумматор и устройства, обрабатывающие проверочные символы, были полностью независимыми.
Благодаря этому исключается возможность такого воздействия ошибки, появившейся в одном разряде, на сумму и проверочный символ одновременно, в результате которого либо ошибка вообще пе будет обнаружена, либо не будет исправлена надлежащим образом. В этом разделе показывается, что если сумматор и проверяющее устройство независимы, то проверочный символ для заданного числа должен быть либо дубликатом этого числа (возможно, подругому закодированным), либо вычетом некоторой кодовой формы этого числа по модулю Ь для некоторого Ь.
Кроме того, показывается, что каждому АЛпкоду соответствует код, основанный на вычислениях по модулю А с тем же самым минимальным расстоянием и по существу с той же самой избыточностью. Рассмотрим систему, изображенную на фиг. 15.2. Здесь через С(гч) обозначен проверочный символ, соответствующий числу Ф, а через: обозначена операция„совершаемая проверочным устройством. Требуется, чтобы выход проверочного устройства совпадал с выходом сумматора, т.
е. чтобы С (Л, ) * С (И ) = С ((У, + 1У,), (15.11) Это накладывает на код ограничения очень специального типа, с(й,) ) — ) с(я,)«с(в~) = с(нг) -с(и,«нг) фиг. !З.й. Система с раздельными сумматором и вроверочвым устройством. Теорема 15.8. Если число проверочных символов меньше оби)его числа элементов в допустимой области целых чисел и проверочный символ С(И) удовлетворяет соотношению (15.11), то С(И) дол- жен быть вьшетом числа Ф„взятого в некоторой закодированной форме по модулю некоторого основания Ь, где Ь вЂ” число различ- ных проверочных символов, а знаком (е) в уравнении (15.11) обо- значено сложение по модулю Ь.
Доказательство. Пусть 5 — совокупность всех целых чисел Л', проверочные символы для которых совпадают с проверочным сим- волом для О, т. е. 5 — совокупность всех целых чисел У, удовле- творяющих соотношению С(У) = С(0). Доказательство теоремы начнем с доказательства того, что 5 — идеал в кольце целых чи- сел. По определенизо 0 принадлежит совокупности 5. Заметим, что С(0) = С(0+0) = С(0)«С(0), и, следовательно, С(0)«С(0)« ...
... и С(0) = С(О) независимо от того, сколько сомножителей стоит слева. Таким образом, если а принадлежит 5, то Фа = а+ ... ... + а также принадлежит 5, ибо С()т'а)=С(а+а+ ... +а) =С(а) еС(а) е... вС(а) = =С(0) еС(0)е... в С(0) =С(0). Кроме того, если а принадлежит совокупности 5, то С ( — а) = С (Π— а) = С (О) е С ( — а) = С (а) а С ( — а) = = С (а — а) = С (0), и поэтому — а также принадлежит 5. Таким образом, 5 — идеал. Далее, заметим, что С(№) = С(йв) тогда и только тогда, когда целые числа № и Л)а лежат в одном и том же классе вычетов по 5.
Это доказывается следующим образом: С (№) = С (№) е С (№ — №). Если № и )Чт лежат в одном и том же классе вычетов, то разность Л)в — № принадлежит идеалу 5 и С(№ — №) = С(0). Поэтому С (Лт) = С (№) е С (0) = С (Уз + 0) = С ( У 1). С другой стороны, если С(№) = С(Фт), то С (Ув — Л),) = С (Ит) е С ( — №) = С (№) е С ( — Л~,) = С(№ — Л~,) = С(0), и поэтому разность )Уз — Й~ принадлежит идеалу 5, а 1чз и Л', лежат в одном и том же классе вычетов по Б. Это означает, что если два различных целых числа У~ и Уз имеют один и тот же проверочный символ, то идеал 3 нетривиалеи, потому что в этом случае С(О) = С(Л~ — Фз), так что идеал, помимо О, содержит по крайней мере еще один элемент.
В соответствии с утверждением теоремы 5.2 идеал 5 является главным идеалом. Это означает, что идеал состоит из всех чисел, делящихся па некоторое целое число Ь. Классы вычетов являются классами вычетов по модулю Ь. Таким образом имеется взаимно однозначное соответствие между классами вычетов и проверочными символами. Для каждого 1, 0 (1( Ь, рассмотрим С(1) в качестве кода для класса вычетов, содержащего 1, т.
е. положим С(1) =1. Тогда 1а)= С(1)а С(1) = С(1+1) =1+1 по модулю Ь. Таким образом„проверочная операция состоит в сложении по модулю Ь. Ч. т. д. Если проверочных символов столько же, сколько чисел, то каждое число имеет отличный от остальных проверочный символ, а проверяющее устройство эквивалентно дублирующему сумматору. Рассмотрим, далее, АЛ'-код с расстоянием, измеряемым в системе по основанию г. Пусть т — наименьшее целое число, либо равное„либо большее 1оя'„А. Тогда каждое целое число, меньшее чем А, может быть записано как т-значное число по основанию г. Рассмотрим код, в котором проверочный символ С(й) для числа У равен вычету числа — г'"Ж по модулю А: — г У=Аз+ С(И).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
