У. Питерсон - Коды, исправляющие ошибки (1267328), страница 98
Текст из файла (страница 98)
В последнем случае в представлении числа Л'з — И~ имеется ненулевое слагаемое (Ь; — а;)2', так как перенос нз позиции 1 — 1 невозможен. В первом же случае имеем слагаемое 2Ь;2' = Ь;2'+'. Но поскольку ни одно из представлений чисел Ш~ и Уз не содержит пары соседних ненулевых слагаемых, то Ьгы = а;.ы = — О и слагаемое Ь;2гы остается в представлении числа Л~з — Уь Если таким же образом объединить все пары а;2' и Ь;2', то результирующее выражение имеет вид (15.2).
Так как пе все коэффициенты равны нулю, то Л~ — Ж~ чь О, и поэтому два различных представления суть представления неравных чисел. Ч. т. д. Это доказательство показывает, как представить в каноническом виде любое число и тем самым определить его арифметический вес. Так, например, число 431 в двоичном виде представляется как ! ! О! 01! 1 1 илн 431= 2з+2г+ 0 + 2з+О -1-2з ! 2з ! 2 ( = йа+ 2'+ 0 + 2з+ 2э + 0 + 0 -! О = 2з + 2'+ 2з + 0 — 2' -!- О -! О -( О 2'+ 0 + 0 — 2~ + 0 — 2'+ 0 + 0 + Π— 1, и его вес равен 4, поскольку в окончательном представлении количество ненулевых членов равно 4. Ниже представлены арифметические веса первых нескольких чисел 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 2 1 2 2 2 1 2 2 3 2 3 2 2 1 17 !8 19 20 2! 22 23 24 25 26 27 28 29 30 31 32 2 2 3 2 3 3 3 2 3 3 3 2 3 2 2 1 Рассматривая записанный выше перечень чисел и весов, можно заметить следующее [46).
Вес любого числа, начиная с 2'+1 и вплоть до числа 2'+2' — ', на единипу больше, чем вес чисел от 1 до 2'-'. Веса чисел, начиная с 2*'+ 2'-'+ 1 и вплоть до 2'+', совпадают с 2' — ' весами чисел 2'+ 2ьл — 1, 2'+ 2' — ' — 2, ..., 2'. Теоремы, из которых следует этот факт, сформулированы в виде задач 15.2 и 15.3. Эти теоремы позволяют записать веса последовательных чисел без их представления в двоичной записи с помощью очень простых вычислений. 15.3. Арифметические коды Рассмотрим теперь код, в котором число У кодируется а числами, представляющими число А!у в системе счисления по основанию г, где А — постоянная величина.
Заметим, что АУ~+ А!Уз=А(!У, + Фз), (15.4) так что кодовая последовательность для суммы двух чисел совпадает с суммой кодовых последовательностей для отдельных слагаемых. Следовательно, закодированные числа могут суммироваться при помощи обычного сумматора. Так как сумма закодирована соответствующим образом, то в ней можно исправлять и обнаруживать ошибки. Если основание г входит в число А в качестве множителя, то г входит в качества множителя также в каждое закодированное число АУ. В этом случае в представлении чисел по основанию г цифра, соответствующая низшему разряду, всегда равна 0 и поэтому будет бесполезной.
Аналогично если А и г не являются взаимно простыми, то в младших разрядах некоторые цифры никогда не появятся. Это нежелательно, и поэтому будет предполагаться, что числа г и А взаимно просты. Интересна аналогия с циклическими кодами. В АУ-коде некоторое число является кодовым, т. е. закодированной формой некоторого другого числа, тогда и только тогда, когда оно делится на А и не выходит из рассматриваемой области чисел. Многочлен определяет кодовый вектор циклического кода, порожденного многочленом д(Х), тогда и только тогда, когда он делится на п(Х) и имеет степень, меньшую чем и. В развиваемой далее теории встречаются и другие аналогии.
В следующих разделах приводятся коды, аналогичные циклическим кодам Хэмминга, кодам максимальной длины и кодам Файра. Однако еще не найдены коды, аналогичные БХ"1-кодам или другим важным классам циклических кодов. Для любого' числа А, такого, что (А. г) = 1, существует наименьшее число и, при котором и" — 1 делится на А.
Если а — количество символов в кодовом слове, то любой циклический сдвиг кодового слова также является кодовым словом, так как циклический сдвиг числа У=а„-~г"-'+а„зу -'+ ... +аз дает число а -зг" ' + а„-зг'-'+ ... + а0г + а,, = г)у — и„, (г — 1), которое делится на А. Прежде всего, как и в случае циклических кодов, если кодовая длина больше чем и, то число г" — 1 нвляется кодовым словом, что дает минимальное расстояние, равное 2. Поэтому кодовая длина должна либо равняться и, как в циклических кодах„ либо быть несколько меньше.
Полученные в этом случае коды аналогичны укороченным циклическим кодам. Число знаков, требуемое для представления числа 1У в системе счисления по основанию г, равно наименьшему целому числу, превосходящему 1о9„У. Число знаков, требуемых для представления А!У, равно наименьшему целому числу, не меньшему чем 1од„(АЛ1) = 1од,. Ф + !од„А. Величина 1о9„А будет называться избыточностью кода; число избыточных символов, требуемых для представления числа А)У, отличается от величины 1од,А меньше чем на 1. Пример.
В 29Ф-коде при г = 2 избыточность равна 1одз 29 = 4,8. Все числа, меньшие чем 2з = 512, могут быть записаны при помощи 9 двоичных знаков. Для того чтобы записать числа 29!У при всех У, меньших 2г, в двоичной фоРме, тРебУетсЯ 14 знаков. Таким образом, фактически необходимо 5 избыточных знаков. В ЗИ-коде при «= 2 избыточность равна !оягЗ= 1,6. Если З)ч код используется для двоичного представления десятичных цифр, то Ж ( 1О. Чтобы представить в двоичной форме все числа, меньшие 10, требуется 4 двоичных знака.
Только 5 двоичных знаков требуется для того, чтобы представить в двоичной форме числа вида ЗФ, и, таким образом, здесь фактически необходим только один избыточный двоичный знак. Для обнаружения одной ошибки требуется, чтобы минимальное расстояние между кодовыми числами равнялось 2, т.
е. чтобы ни- какие два кодовых числа не отстояли друг от друга на расстояние, равное 1. Таким образом, нужно чтобы при всех допустимых зна- чениях Ф1 и Из А У1 — АФ, = А (Ф~ — )уг) Ф Ь«~, (15.5) где 0 ( Ь ( «. Для того чтобы добиться выполнения этого условия, в качестве А следует выбрать некоторое взаимно простое с «число, превосходящее «. В частности, всегда можно положить А = «+ 1, Любой ЗФ-код будет обнаруживать все одиночные ошибки в двоичном представлении, а 11У-код — все одиночные ошибки в десятичном представлении чисел.
Следовательно, для обнаружения одной ошибки при любом заданном основании требуется фиксированная избыточность, не зависящая от того, насколько велико число Ф. Необходимая избыточность равна 1од„(«+ 1), а это значит, что всегда будет требоваться не менее одного и не более двух дополнительных символов. Это соответствует тому факту, что с помощью одного проверочного символа в обычном линейном коде будут обнаруживаться лишь одиночные ошибки независимо от того, сколь велика длина кода. Теорема 15.2.
АИ-код может исправлять все комбинации из 1 ошибок тогда и только тогда, когда все числа веса 1 или меньше имеют р зличные вычеты по модулю А. Доказательство. Предположим, что различные числа Ф1 и Ф, с весом 1 или меньше имеют равные вычеты. Тогда вычет числа Ф1 — Фг равен О, т. е. это число кратно А и, следовательно, является кодовым. Но вес числа Ф, — Фг равен по крайней мере 21, т. е. код не может исправлять все 1-кратные ошибки. С другой стороны, пусть минимальный вес кодового слова равен 21+1. Тогда, если Ф, и Уз — различные числа веса 1 или меньше, то у них должны быть различные вычеты, ибо в противном случае У, — Ж, должно быть кодовым словом с весом, меньшим чем 21+ 1. Ч.
т. д. Коды с минимальным расстоянием, большим 2, удобнее всего характеризовать величиной М„(А, д)„определяемой как наимень- Габдаца 16.1. 4(ноачиые А((7-коды Коды с ряссеоянием 4 Коды с рясстоянисм 3 АМ, (А. 4) Ме (А Э] М,(А, 4) 6(ее число, вес (в представлении по основанию г) произведения которого на А меньше чем (Г. Теорема 15,3. Если 1)7 изменяется в области 0 ( й((М„(А, (Г) или в области — 1/,М„(А,(1 — 1) (Ж( (/яМ7(А, й), то при любых 4 и г минимальное расстояние А(()-кода равно по меньшей мере й. Доказательство, Если числа й(( и ))(г одновременно принадлежат энной из областей, указанных в условии теоремы, то 1((1 — Л(я ( ( М,(А,(1) и А(((1 — АФз ( АМ,(А,(7). Следовательно, по определению величины М,(А,с() вес разности А((7'1 — А(((4 больше чем Ы вЂ” 1.
Ч. т. д. Если не считать способов, которые следуют из приводимых ниже теорем 15.4 и 15.7, то единственным известным способом определения величины М„(А, (() является непосредственное вычисление. Некоторые значения этой величины приведены в табл. 15.1 для наиболее интересных случаев г = 2 н 41 = 3 или 4. !5.4. Совершенные арифметические коды, исправляющие одиночные ошибки Теорема 15.4 (331. Если А — нечетное простое число и 2 — примитивный элемент поля целых чисел по модулю А, то 2( пи+ 1 Мз(А, 3)= (15.6а) 1! 13 19 23 29 37 47 53 59 6! 67 71 79 83 !О! 103 3 5 27 89 565 7 086 178 481 1 266 205 9 099 607 !7 602326 128 207 979 483 939 977 6 958 934 353 26 494 256 09! 5 099 523 830 125 1! 360134!13449 43 6! 89 !06 !53 !85 267 35! 363 357 393 547 555 737 80! 3 5 23 39 215 1 417 !5709 23 905 25 249 46 995 181 433 245 131 123 818 877 5 967 134 431 Ю 98! 392!59 27 2б 211 2!7 2'б + 214 222 244 + 273 + 27' 274 + 277— 214 241 2" + +! — 1 — 1 — 1 27 — 1 +1 — ! 211 2" +1 — ! 277 +1 217 +! — 1 2'б — ! 2Я' — 1 Если элемент — 2 примитивен по модулю А, а элемент 2 не прими- тивеН то в(л-пп Мз(А, 3) = (15.6б) О, наоборот, если выполняется равенство (15.6а), то А — простое число, а 2 — примитивный элемент по модулю А, а если выполняется равенство (15.6б), то Л вЂ” простое число и элемент — 2 примитивен, а элемент 2 не примитивен по модулю А.
Доказательство. Если А — простое нечетное число, то 2л ' — 1 = (2(л — пп -[- 1) (2!л — 'Ф вЂ” 1) = О по модулю А. Если 2 — примитивный элемент по модулю А, то 2<л "~э+ 1 = О, или 2<л-па = = — 1, так как 2гл — Ш' Ф 1. Тогда все вычеты по модулю А чисел 1,2,2з, ..., 2~л — На 2(л-Пп = — 1 — 2 ... — 2<л-эх~, представляющих ошибки веса 1, различны.
Поэтому из теоремы 15.6 следует равенство (15.6а). Если — 2 — примитивный элемент и А — простое нечетное число, то числа 1, 2, 2з, ..., 2гл — Ып будут различны, так как различны их квадраты 1, ( — 2)з, ..., ( — 2)<л — Н. Кроме того, среди них не может быть числа, равного — 1, так как если 2! = — 1 по модулю А для некоторого !((А — 3)/2, то 2з!=1 ( — 2)тя по модулю А для некоторого числа 21, удовлетворяющего неравенству 2! (А — 3. Но это невозможно, потому что по предположению — 2 — примитивный элемент. Снова (2гл — Пп — 1) (2гл Пп+ 1) = О по модулю А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
