У. Питерсон - Коды, исправляющие ошибки (1267328), страница 97
Текст из файла (страница 97)
Постройте декодер для БПМ-кода с пс = 4 со степенью перемежения й Декодирование проводите независимо по потокам из ! символов. 14.8. Покажите, что количество запоминающих устройств, требуемых для БПМ-декодера типа декодеров, построенных в задачах 14.7 и 14.6, равно !!па(2ле — 1) — 1) 14.9. Постройте декодер, исправляющий одиночные пакеты, для кода из задачи 14.7. (См. равд. !4.2.) Сравните с декодером из задачи !4.7. 14.10.
Покажите, что количество запоминающих устройств, используемых в декодере Ивадаре, равно (и> — 1) ((2по — 1) 1+ "' "~ ) + ! + ао — 2. Сравните с результатами задачи 14.8. 14.11. Покажите, что в кодах Ивадаре не происходит размножения ошибок. 14.12. Рассмотрите сверточпый (гппм шйа)-код, который может исправлять все комбинации ошибок веса ! = гпе или меньше.
Если этот код подвергается блоковому перемежепию степени й то он может исправлять все одиночные пакеты длины г! или меньше. Приведите что-либо определенное о корректирующей способности этого кода для многократных пакетов. 14Л3. Постройте четыре ортогональных соотношения для сверточного (18,9)-кода, для которого ~100100011)т (100000000) ' Выберите эти соотношения так, чтобы Ь = 4. Сравните с самоортогональным диффузным кодом из примера равд. 14.5. 14.14. Определите эффективную длину ограниченна для (18,9)- кода нз задачи 14.13 и самоортогонального (20, 10)-кода из равд.
14.5. (См. задачу 14.13.) Для какого кода вероятность первой ошибки меньше при передаче по ДСК? 14Л5. Сравните максимальную и среднюю величины защитного пространства, требуемого для блокового и сверточного кодов при й = '/ь Обсудите выводы. 15 Арифметические коды Коды, рассматриваемые в этой главе, отличаются от всех кодов, изучавшихся выше, тем, что связанные с ними операции являются обычными арифметическими. Эти коды важны с прикладной точки зрения. Они могут быть использованы при обработке информации, если кодирование проводится неспециализироваиной вычислительной машиной, нли для проверки работы сумматора. Существует интересная аналогия в структуре арифметических и циклических кодов. 15.1. Определение понятий «ошибка» н «расстояние» Будем предполагать, что числа представлены в виде многочлена по степеням основания г: У= У -1г" '+ У»-оФ -'+ ...
+ У1г+ Уо. (15.1) где 0 ( У( г и 0 ~ У~ «, г. Число У записывается в виде У„,У„о ... У,Уо. Важнейшие частные случаи такого представления чисел — это двоичная система счисления, где г = 2, н десятичная система счисления, где г = 10. Количество цифр и является длиной кода. Лример. Двоичное число И 010 = 1 Х 2о + 1 Х 2» + 0 Х 2'+ 1 Х 2+ 0 Х 1, что дает в сумме 26. Десятичное число 382 обозначает З)(10з+ +8Х10+2.
Ари4гоетический вес числа У определяется как минимальное число ненулевых слагаемых в представлении этого числа в виде У=а„г +а, ~г" '+ . +ао (15.2) где целые числа а, могут быть положительными или отрицательными, но по абсолютной величине должны быть обязательно меньше чем г. Вес числа У должен быть меньше числа ненулевых членов в выражении для У, включающем члены степени п+ 1 или больше. (См.
задачу 15А.) Арифлегическое расстояние между двумя числами У~ и Уо определяется как вес разности У, — Уэ Если передано число у~ и получено число й!з ~ !уь а расстояние между й!, и 7Уя равно г1, то говорят, что появилась й-кратная ошибка. Таким образом, появление й-кратной ошибки в числе !У~ эквивалентно добавлению к !У, числа веса й. Отметим, что при таком определении расстояние зависит от выбора основания г. Нетрудно показать, что так же, как и в случае расстояния Хэмминга, для обнаружения всех ошибок кратности г! — 1 или меньше необходимо и достаточно, чтобы расстояние между любой парой кодовых чисел было не меньше чем г1. Для исправления любой комбинации из ! или меньшего числа ошибок необходимо и достаточно, чтобы минимальное расстояяие было равно 2!+ 1.
Вообще для исправления любой комбинации из ! или меньшего числа ошибок и одновременного обнаружения любой комбинации из й или меньшего числа ошибок требуется, чтобы расстояние было не меньше чем !+й+ 1. Пример. В случае г= 2 расстояние между числами 171 и 203 равно 1, так кек 171 — 203 = — 32 = — — 2з. Расстояние между числами !7 и 32 равно 2: 17 — 32 = — 15 =— +2е — 2'. В случае десятичной системы счисления расстояние между числами 1296 и 1193 равно 2, так как 1296 — 1193 = 1 Х 10з + 38 Х 10а.
Расстояние между числами 1296 и 1305 равно 1, несмотря на то, что они отличаются в трех знаках, так как 1296 — 1305 = — 9 Х 1Оа. Арифметическим расстоянием в контексте этой главы пользоваться удобнее, чем расстоянием Хэмминга. Оно более правильно отражает типы ошибок, которые могут появляться в процессе работы арифметических устройств вычислительных машин. Ясно, что если произошла ошибка в одном знаке, то это одиночная ошибка. Если произошли ошибки в ! знаках, то это самое большее 1-кратная ошибка. Таким образом, устройство, которое может исправлять все ошибки кратности ! или меньше в описанном выше смысле, правильно исправляет все числа, в которых изменилось не более чем ! знаков. Однако в сумматоре одна ошибка в одном разряде из-за переносов может привести к тому, что ошибки появится в нескольких разрядах.
Ошибка при переносе также может повлиять на несколько разрядов. При введенном определении расстояния такие ошибки трактуются тем не менее как одиночные! Нетрудно построить параллельные двоичные сумматоры для вычислительной машины так, чтобы ошибка в одном разряде сумматора влияла не более чем па один разряд суммы или на один перенос. Код, исправляющий 'все одиночные ошибки, будет исправлять ошибку в любом разряде сумматора, несмотря на то, что из-за переноса могут Оказаться неверными несколько разрядов результата, 15.2. Свойства арифметического веса в двоичном случае Будем теперь предполагать, что т = 2. Тогда как вес числа вполне определен и единствен, выражение того типа, которое входит в равенство (15.2), не единственно. Например, 3 = 2+ 1 = = 4 — 1 и, таким образом, вес числа 3 равен 2, но существуют два различных выражения, на которых достигается минимум числа ненулевых слагаемых, равный двум.
Однако для каждого числа имеется каноническая форма, которая содержит минимальное количество слагаемых, Теорема 15.1. Для любого числа й> существует единственное представление вида >ч =а„2" +а„,2 ->+ ... +а„ в котором ач = ~ 1 или О и не существует двух соседних козффиииентов, отличных от нуля. Это представление содержит минимальное количество ненулевых членов. Доказательство.
Сначала покажем существование такого представления с минимальным количеством членов; а затем установим его единственность. Пусть )У = Ь„2. + Ь„ ,2. — + ... + Ь,. (15.3) Если существует два соседних, отличных от нуля коэффициента Ьь то пару с наименьшим 1 обозначим через Ь<+>2'+'+ Ь;2'. При Ь; = — Ь;м справедливо равенство Ь|~>2+>+ Ь;2*'= Ь~Н2' и количество единиц в выражении для У уменьшится. Если Ь; = Ьььь то Ь,+,2*'+'+ Ь;2' = Ь; ы2'+» — Ь,2'. Сделав такую подстановку в выражение (15.3), получим коэффициент при 2'+' равным нулю. Слагаемое Ь„+,2*'+» может быть объединено с уже имеющимся слагаемым Ьмв2'ь». Если Ь;+х равно нулю, то новое представление имеет то же количество слагаемых, что и первоначальное.
При Ь;+а = — Ь;ъ, эти слагаемые взаимно уничтожаются и представление содержит меньшее количество слагаемых. Если Ь;+» = Ьсьь то объединение дает Ь;~.,2'+»+Ь;м2'+» Ьсы2'+а и коэффициент при 2'+г становится равным нулю, тогда как слагаемое Ь,+,2'+' должно быть теперь объединено со слагаемым Ьсь»2'+а. «Перенос» может продолжаться до члена наивысшего порядка, но каждый раз, когда происходит перенос, количество ненулевых членов уменьшается. Таким образом, результирующее выражение имеет ту же общую форму (равенство (15.3)1 количество ненулевых слагаемых в пем не больше, чем в первоначальном выражении, и нет двух последо.
нательных ненулевых слагаемых степени, меньшей чем 1+ 2. Если этот процесс повторить, то результирующее выражение не будет содержать двух соседних ненулевых слагаемых, а коли-. чество слагаемых будет не больше, чем у первоначального выра- жения. Этот процесс, конечно, закончится, ибо на каждом шаге среди слагаемых малого порядка остается по меньшей мере два слагаемых, причем отсутствуют пары соседних ненулевых слагаемых, а их общее количество не больше, чем первоначальное, которое, очевидно, ограниченно.
Если первоначально выбранное представление имеет минимальное количество слагаемых, то количество слагаемых не может уменьшиться и окончательное представление должно иметь столько же слагаемых. Поскольку для каждого числа существует представление вида (15.2) с минимальным количеством слагаемых, то, следовательно, любое число имеет представление с тем же самым минимальным количеством слагаемых, в котором отсутствуют соседние ненулевые слагаемые. Остается показать, что такое представление единственно.
Вопервых, заметим, что если старший коэффициент в разложении вида (15.2) с коэффициентами ~1 и О равен +1, то число )У принимает наименьшее значение, когда все другие коэффициенты равны — 1. В этом случае У„ы=2" — 2" ' — 2" э — ... — 1=1. Аналогично, если старший коэффициент равен — 1, то наибольшее значение для Л' равно — 1. Таким образом, если в представлении числа а„ = О, то число равно нулю тогда и только тогда, когда все коэффициенты равны нулю. Пусть теперь К~=а 2" +л„~2"-'+ ...
+по, Же= Ь„2" + Ь„,2"-'+ ... + Ьм и предположим, что в каждом из этих представлений отсутствуют соседние слагаемые, отличные от нули, и по меньшей мере для одного коэффициента а; ~ Ьь Тогда )тх — )У~ =(܄— а ) 2" + (Ь„~ — а„~) 2"-'+ ° + (Ь0 — а0). Теперь если а~ ~ Ьь то возможны два случая: либо а; = — Ьь либо один из этих коэффициентов равен О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
