У. Питерсон - Коды, исправляющие ошибки (1267328), страница 26
Текст из файла (страница 26)
Итак, прослеживая вывод неравенств (4.33), получаем получаем верхнюю границу для усредненной величины Р,„ по всем кодам с г! ) Йа. По теореме 4.9 число таких кодов равно по меньшей мере 2 ""'~ ' '; таким образом, при усреднении это число может быть использовано вместо действительного числа кодов. Иаконец, по крайней мере один код в классе столь же хорош, как и средний, и верхняя граница для величины Р,, справедлива также и для этого кода. Полученная граница идентична соответствующей границе для блоковых кодов из теоремы 4.10 с заменой Ре на Р1 Разумеется, асимптотическое поведение границы при и, стремящемся к бесконечности, также идентично поведению границы для блоковых кодов.
Эта асимптотическая граница представлена соотношениями !4.40), !4.42) и !4.43) и изображена на фиг. 4.3 для Р= 10 Для получения нижней границы величины Р~,— вероятности первой ошибки — можно воспользоваться верхней границей Плоткина для минимального расстояния, полученной в прсдыдущем разделе. Способ рассуждений при этом такой же, как и для блоковых кодов. Пусть через г! обозначено наибольшее минимальное расстояние, допускаемое границей Плоткина. Вероятность Р,, не меньше, чем вероятность спутать переданное слово с другим словом, отстоящим от него на расстоянии д.
Таким образом, для двоичного симметричного канала !ДСК) !4.58) ! та+ юю где г! удовлетворяет соотношению 14.50). При больших значениях л и г1 надежность Е удовлетворяет следующим неравенствам: Е( — 1ип — 1одР„( — Е(0,5, Р), !4.59) где функция Е!Х, Р) определена в приложении А. Используя асимптотическую форму границы Плоткина, неравенство 14.51), получаем 1! — Р) Е(Ц5, Р) ! — )! 1 ! 2 2 44РО Эта граница изображена на фиг. 4.3 при Р = — 10-2.
Как можно видеть, при скоростях передачи, близких к пропускной способности капала, граница очень неточна. Используя прямолинейную границу н границу сферической Упаковки для блоковых кодов, можно определить нижнюю границу дли Р, средней вероятности ошибки для наилучшего сверточного кода. Эта граница также справедлива для более широкого класса древовидных кодов. О ие О % сг ггь йп ьуаурасвь Фиг. 4.3. Графики границ иадежности как функции скорости для систематичегсих сверточгвсх кодов при передаче по двоичиому симметричпому каналу : Р=ООП Ц-граница елучайиого кодировисшя; Б — граиица Платиииа; и — граиица сферической уиасовка для ияоковыд кодов.
Рассмотрим линейный древовидный (йчпмтйо)-код, используемый при передаче по ДСК с вероятностью ошибки Р. Будем предполагать, что код является систематическим. Предположим, далее, что передано Б блоков, состоящих из по символов. За ними последуют проверочные символы в пу — 1 последующих блоках.
Итак, пусть переданы все проверочные символы для всех информационных символов. Возникающую при этом совокупность из 2ий кодовых слов можно рассматривать как линейный блоковый код длины под+ +(но — йо) (и — 1). Вероятность ошибочного декодирования для Теперь рассмотрим коды достаточно большой длины и обозначим через р отношение В/т. При условии, что и — постоянная величина, надежность древовидного кода Е, представляется в виде 1 Е~= — 1пп — 1оаР,=(р+ 1 — /1с) Е„ л~лс где К~ = й0/и,, а через Еь обозначена верхняя граница надежности блокового кода.
Скорость передачи для блокового кода Лс в+1 — Л~ ' (4.63) Поскольку равенстно (4.62) справедливо при всех значениях параметра р, то наилучшая верхняя граница для Е, получается, если выбрать нижнюю огибающую семейства границ. Этот результат приведен на фнг. 4.3 для Р = 1Π— з. Следует отметить, что поскольку прямолинейная граница и граница сферической упаковки справедливы для более общих дискретных каналов без памяти, то для них справедлива и только что полученная граница. 4.6. Границы для кодов, исправляющих и обнаруживающих пакеты ошибок Пакетом длины 1 называется вектор, ненулевые компоненты которого имеются только среди 1 последовательно расположенных компонент, первая и последняя из которых отличны от нуля, этого блокового кода ограничена снизу границей сферической упаковки н прямолинейной гранипей из разд.
4.2. Эти границы справедливы для любого кода и любого способа декодирования. В частности, они справедливы, если построенный вьнце код декодировать как древовидный код. Обозначим через Р, среднюю вероятность того, что блок, составленный из пз символов, декодируется нсправилыю при условии, что код декоднруется как древовидный код. Очевидно, что Р, не меньше, чем средняя вероятность того, что блок ошибочен, при условии, что код рассматривается как блоковый и декодирование производится по принципу максимального правдоподобия. Эта последняя вероятность в свою очередь ограничена снизу величиной нижней границы вероятности ошибки для блокового кода, умноженной на 1/В, поскольку когда появляется ошибочное слово, то по крайней мере один блок должен быть ошибочным.
'Таким образом, для древовидного (тпм тй0)-кода 1 1всличина нижней границы вероятности) Р,.~ — ~ошибки для наилучшего блокового ~ . (4.61) (Вп, + (и — 1) (и0 — йз), Вйз)-кода Теорема 4.13. Линейный блоковый код, который не содержит пакетов длины 1 или меньше в качестве кодовых слов, должен иметь по крайней мере 1 проверочных символов. Доказательство. Если среди кодовых векторов нет пакетов длины 1, то ни в каком смежном классе не существует двух векторов, имеющих нули всюду, кроме 1 первых компонент, потому что если бы такие два вектора нашлись, то их разность, которая должна быть пакетом длины 1 или меньше, должна была бы быть кодовым вектором.
Число векторов, для которых только 1 первых компонент отличны от нуля, равно д' и, следовательно, должны существовать по крайней мере 4г смежных классов и по крайней мере 1 проверочных символов. Ч. т. д. Теорема 4Л4. Для обнаружения линейным блоковым кодом длины и всех пакетов ошибок длины 1 или меньше необходимо и достаточно иметь 1 проверочных символов. Доказательство. Необходимость следует из теоремы 4.13. Достаточность следует из того факта, что все пакеты ошибок длины 1 или меньше обнаруживает код„у которого первые и — 1 символов информационные, а последние 1 символов — проверочные символы, выбранные так, чтобы обращалась в нуль сумма любого из 1 наборов символов, образованного одним из первых 1 символов и всеми символами, которые расположены в кодовой последовательности через 1 символов друг от друга, начиная с первого, включенного в набор. Тогда иа каждый фиксированный проверочный символ оказывает влияние самое большее один из ненулевых символов пакета ошибок длины 1 или меньше, и, таким образом, каждый такой пакет ошибок будет обнаружен наряду со многими другими комбинациями ошибок.
Ч. т. д. Проверочная матрица для такого кода при и = 23 и 1 = 5 имеет вид 10000100001000010000100 010000!0000!0000!000010 0010000100001000010000! 00010000100001000010000 00001000010000!00001000 метод практической реализации этой матрицы при помощи регистров сдвига иллюстрируется фиг. 4.4. Это элементаряый пример циклического кода 1см. гл. 8). Теорема 4.15 1252).
Для того чтобы линейный код исправлял все пакеты ошибок длины Ь или меньше, он должен иметь по крайней мере 2Ь проверочных символов. Чтобы линейньш" код исправлял пакеты ошибок длины Ь или меньше и одновременно обнаруживал фиг. 4.4. Регистр сдвига для иычисления проверочных символов (рз, 18)-кода при 1 о. все пакеты ошибок длины 1) Ь или меньше, он должен содержать по крайней мере Ь + 1 проверочньгх символов, Доказательство.
Любой вектор, имеющий форму пакета ошибок длины 2Ь нли меньше, может быть записан в виде разности двух пакетов ошибок длины Ь илн меньше (за исключением вырожденного случая, когда пакет содержит единственный ненулевой элемент). Так как, для того чтобы исправлялись все пакеты ошибок длины Ь или меньше, необходимо, чтобы они принадлежали различным смежным классам, их разности не могут быть кодовыми словами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
