У. Питерсон - Коды, исправляющие ошибки (1267328), страница 99
Текст из файла (страница 99)
Если (А — 1)/2 — четное число, то 2(л-ПФ = =( — 2)<л — 'и чь 1, откуда следует, что 2гл — ма =[1. Следовательно, 2 — примитивный элемент, и выполняется соотношение (15.6а). Если, с другой стороны, — 2 — примитивный элемент, а 2 — непримитнвный элемент, то число (А — 1)/2 должно быть нечетным. Тогда 2гл — Пп — 1 = О и вычеты чисел 1, — 2, 2з, ..., 2!л-зтз, — 1, -[-2, — 2', ..., — 2!л-вп, представляющих ошибки веса 1, различны.
Поэтому в соответствии с теоремой 15.2 справедливо соотношение (15.5б). И обратно, из теоремы 15.2 следует, что если одно из равенств (15.6а) или (15.6б) выполняется, то все вычеты по модулю А должны быть сравнимы с чт2*', и А должно быть нечетным. Тогда 'число 2, а следовательно, и все вычеты по модулю А взаимно просты с А и число А должно быть простым. Поэтому вычеты по модулю Л образуют поле. Порядок числа 2 равен по меньшей мере (А — 1)!2, поскольку вычеты всех меньших степеней числа 2 различны. Но А — 1 должно делиться на порядок числа 2, т. е. порядок числа 2 равен либо (А — 1)/2, либо А — 1.
То же самое верно для числа — 2. В соответствии с утверждением теоремы 6.20 существует примитивный элемент а. Если порядок элементов 2 и ( — 2) равен (А — 1)/2, то число ~2~ всегда сравнимо с четной степенью а. Но это невозможно. Поэтому порядок одного нз чисел 2 илц — 2 равен А — 1 и соответствующее число есть примитивный эле- мент поля. Ч.
т, д, Коды, описываемые теоремой 15.4, аналогичны совершенным кодам Хэмминга, исправляющим одиночные ошибки. Код„используемый для кодирования чисел из области 0 =' Ф ( 2" (или — 2" — ':-= !т' С 2"-'), должен обладать способностью различать каждую из 2п возможных ошибок и правильное кодовое число, т. е.
всего 2п+ 1 возможностей. Утверждение теоремы 15.2 сводится к тому, что каждой из этих 2п+ 1 возможностей соответствует отличный от других вычет, откуда следует, что А =» 2п+1. В теореме 15.4 приводятся условия, необходимые и достаточные для того, чтобы выполнялось точное равенство. Отметим сходство найденных результатов и соответствующих результатов для циклических кодов. В АА'-коде должно быть простым не только число А, но, кроме того, и число 2 должно быть примитивным элементом.
В случае двоичного циклического кода Хэмминга порождающий многочлен кода д(Х) должен быть неприводимым и его корни должны быть Примитивными элементами. Все перечисленные в табл. 15.1 коды с расстоянием, равным 3, удовлетворяют условиям теоремы 15.4. 15.5. Арифметические коды с большим минимальным расстоянием Пусть А — простое число, для которого число 2 является примитивным элементом. Тогда число 2л-' — 1 делится на А. Положим тл ' — ! в= и рассмотрим В!т'-код. Естественно, что число используемых в кодовом слове знаков равно и = А — 1. Полученный код является арифметическим кодом циклического типа.
Код содержит (2"— — 1)/В = А закодированных чисел, среди которых находятся нуль и А — 1 чисел, задаваемых циклическими сдвигами представления числа В из и = А — 1 знаков. Приведенные ниже теоремы 15.5 и 15.6 раскрывают весовую структуру кода. Теорема 15.5. Если имеет место двоичное представление числа !В=5„д"-'+54 в2"-'+ ... +ь,, оч'!сА, то 5! = (!2" ' пнх1 А) пюд 2. Доказательство.
Имеет место равенство гз !2" — ! Й" А2' А А2' 12" ! — (!2" а!ос А) 1 /' !2" а!оа А А ~ ~ ~ ! ~ ~ ~ ~ ~ з ~ ! ~ ~ | А А2'/ = (Ь - !2' ! ' + Ь -э2" ' о + ° .. + Ь!) + Ь! !2 ! + ... + Ьо2-!. Приравнивая целые части выражений в обеих частях равенства и умножая их на А, гюлучаем 12 -' — (12" ггпойА) =А (Ь„!2" ' '+ Ь„о2"-г-о+ ... + Ь!) и после взятия вычета по модулю 2 имеем — (12 ! гной А) гной 2 = (А гной 2) (Ь!) или, поскольку А — нечетное число, (12" ц пюй А) и!ой 2 = Ьо Следствие 15.1.
В двоичном представлении числа В половина знаков †ну, а половина в единицы. Доказательство, Так как 2 в примитивный элемент по модулю А, то вычетами чисел 2г по модулю А, 1(1 = п — 1, исчерпываются все целые числа между 1 и А — 1. Поскольку половину этих чисел составляют четные числа, а другую половину — нечетные, то половина иа чисел Ь! равна единице„а другая — нулю. Ч. т. д. Теорема !5.5. Пусть А — простое число, большее чем 3, которое имеет 2 в качестве примитивного элемента, и число В =(2"-'— — 1)/А. Арифметический вес любого кодового числа в В/!/-коде равен (А — 1)/3 или (А+ 1)/3 в зависимости от того, какое из этих чисел целое.
Это число представляет собой также арифметическое расстояние между любой парой кодовь!х чисел и равно минимальному расстояншо Хзмминга. Доказательство. Рассмотрим случай, когда (А — 1)/3 — пелое число, и пусть В = Ьо+ Ь,2 + ... + Ь„,2" ', ЗВ = со+ с,2+ ... + с„,2"-!. Тогда 2В=(со — Ьо)+(с! — Ь!)2+ ... +(с„,— Ь„,)2" ' (15,7) и коэффициенты га — Ь; в этом представлении равны либо ~1„ либо О.
В частности, с~ — Ь, = О в соответствии с теоремой 15.5 тогда и только тогда, когда вычеты чисел 2' и (3 2') по модулю А либо оба четные, либо оба нечетные. Если (2''гпобЛ)(А/3, то (3.2'')гпобА = 3. (2'шодА) и (3 2')гпобА четное тогда и только тогда, когда 2' шоб А четное. Если А/3 ((2'гпод А) ( 2Л/3, то (3 2*')гпобА = 3 (2'шос1А) — А, и если (2'шодА) — четное число, то( 3 2*')шодЛ вЂ” нечетное, и наоборот.
Если 2А/3 ((2'шобА) ( ( А, то (3 2') шоб А = 3(2*' гпоб А) — 2А и снова числа (3.2')гподА и (2'шобА) либо оба четные, либо оба нечетные. Таким образом, ненулевые слагаемые появляются в выражении (15.7) при тех й для которых А/З(2гшобА С 2А/3. Поскольку по предположению 2 — примитивный элемент по модулю А, то все целые числа, лежащие между 1 и А — 1, являются вычетами числа 2* по модулю А. Если число А — 1 делится на 3, то имеется (А — 1)/3 таких вычетов. Если число А — 1 не делится на 3, то, так как и А не делится на 3, число А+1 должно делиться на 3 н тогда количество целых чисел, лежащих между А/3 н 2А/3, равно (А+ 1)/3.
Таким образом, в выражении (15.7) имеется (А — 1)/3 или (А + 1)/3 ненулевых слагаемых. Предположим теперь, что Ь; — с; чь О. Тогда вычет числа 2' по модулю А находится между А/3 и 2А/3. Отсюда следует, что число 2ьы шобА лежит между 2А/3 и А, если 2'гпог(А находится между А/3 и А/2, и 2гы шодА лежит между 1 и А/3, если 2'апой А находится между А/2 и 2А/3. В любом случае в силу соображений, приведенных в предыдущем разделе, Ьгы — с;+, — — О. Таким абра. зом, в выражении (15.7) нет двух соседних ненулевых слагаемых. По теореме 15.1 количество ненулевых слагаемых в этом выражении определяет арифметический вес числа 2В.
Любое кодовое слово может быть получено в результате циклического сдвига двоичного представления числа 2В. Рассмотрим кодовое слово, полученное из числа 2В сдвигом на 1 символов влево. Оно может быть также получено после 1 сдвигов влево чисел В и ЗВ и последующего вычитания этих сдвигов.
Полученное выражение будет сдвинутым вариантом канонического представления числа 2В, данного в выражении (15.7). Поэтому любое кодовое слово имеет тот же арифметический вес (А — 1)/3 илн (А + 1)/3. Наконец, в силу того что расстояние Хэмминга не может быть меньше, чем арифметическое расстояние, расстояние Хэмминга будет по меньшей мере (А — 1)/3 или (А+1)/3. Но это как раз и есть расстояние Хэмминга между числами В и ЗВ, т. е.
минимальное расстояние кода. Ч. т. д. Эти коды являются кодами, двойственными к кодам, исправляющим одиночные ошибки, которые описаны в первой части теоремы 15Л. Возникает вопрос, что происходит, если число — 2 представляет собой примитивный корень по модулю Л, а число 2 не является примитивным корнем по модулю А. Ответ заключается том, что тогда существует код, порожденный числом В = (2л — ~ — 1)/А, и, используя следующую далее лемму, можно доказать теоремы, аналогичные теоремам 15.5 и 15.6. Лемма 15.1.
Любое целое число Ж может быть представлено единственным образом в виде Ь1=а„( — 2)" + а„,( — 2)" '+ ... + ам (15.8) где а~ равно О или 1. Доказательство. Прибавим к )У число 2+2'+2ь+ ... '+2', где 2') )у. Сумму представим в двоичном виде с неотрицательными коэффициентами и затем вычтем почленно число 2+ 2з+ ... ... + 2'. В результате получим требуемое выражение.
Из единственности первоначального двоичного представления сразу следует и единственность представления (15.8). Используя выражение (15.8), можно показать также, как это сделано при доказательстве теоремы 15.5, что коэффициенты (15.8) могут быть представлены в виде следующих сравнений: а, =(( — 2)" шод А) шод 2, а отсюда непосредственно следует справедливость утверждения теоремы 15.6. Для арифметических кодов пакет ошибок длины Ь может определяться как комбинация ошибок е = 12', где 2" — ' < 1< 2ь, а 1— нечетное число.
В следующей теореме приводятся коды, аналогичные кодам Файра, и сама теорема представляет в основном интерес как пример аналогии, проводимой между циклическими и арифметическими кодами. Теорема 15.7. Если А' — простое число и 2 — примитивный корень по модулю А', то арифметический код, порожденный числом А'(2' — 1), длины и, равной наименьшему общему кратному чисел с и А' — 1, может исправлять произвольный одиночный пакет длиньь Ь, если 2Ь < с и А' ) 2ь. Доказательство из-за его идейной простоты и довольно большой длины здесь не приводится. В работе 148) даются и некоторые другие обобщения подобного типа. 15.6.
Самодополняющиеся АУ+ В-коды Для некоторых целей бывает желательно, чтобы код для дополнительного числа был дополнительным кодом для самого числа [331. Если числа, подлежащие кодированию, имеют основание Ь, то дополнение числа Ф определяется как Ь вЂ” 1 — !У. Если кодовое число может быть представлено в виде и-значного числа по основанию г, то дополнение числа А!У определяется как г"— — 1 — А!У.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
