У. Питерсон - Коды, исправляющие ошибки (1267328), страница 22
Текст из файла (страница 22)
При таком способе построения проверочной матрицы можно быть уверенным в том, что никакая линейная комбинация из й — 1 нли меньшего числа столбцов матрицы не обращается в нуль. Очередной столбец может быть присоединен к матрице в том случае, если совокупность всех линейных комбияаций из й — 2 или меньшего числа предыдущих столбцов матрицы не исчерпывает всех наборов длины г. В наихудшем возможном случае все такие линейные комбинации будут различными. Всего имеется д — 1 возможных ненулевых коэффициентов линейных комбинаций; таким образом.
чпсло всевозможных линейных комбинаций нз й — 2 нли меньшего числа столбцов, выбранных из общего числа ! — 1 столбцов, равно С' ,(а — ц + С ,(д — !) + ... + С~~ (а — !)" ° (4 !9) Есл ели это число меньше, чем д" — 1, общего числа отличных от куля наборов длины г, то наверняка найдется еще один столбец, который может быть присоединен к матрице. Итак, если С,',(д — ц+С,'-,(д — ц'+ ...
... +С,":,'(д — Ц"-'<у' — 1, (4.20) С„'(у — Ц+С'.(д — Ц'+ ... +С'„-'(д — Ц"-'~у' — 1. (4.2Ц Таким образом, получена нижняя граница для минимального расстояния (и., й)-кода. Теорема 4.7. Существует (и, й) -код с минимальнь ~ расстоянием, равным по меньшей мере й, который удовлетворяет следующему неравенству: Х С„'(д — Ц' ~ у.-'. Е П Для больших значений и можно получить асимптотические результаты, если воспользоваться формулами, приведенными в приложении А. Например, для случая у = 2, используя границу Чернова (А.8) и соотношение (А.10), находим 2"-'»~' С„'= ~ С„*» 8=О и-л+з ( . )" '( .) и — в+21 М + ~Си — 2Ъ ~ ! ин1М-зуь] или, логарифмируя обе части, имеем и — й»и7Т(В „), (4.22) Эта граница изображена на фиг.
4.! в предположении; что й и и настолько велики„ что в правой части неравенства (4.22) можно пренебречь числом 2, то существует код из ! символов самое большее с с проверочными символами (и, следовательно, самое меньшее с й = ! — г информационными символами) и с минимальным расстоянием й. Этот код является нулевым пространством матрицы размерности т Х1, которая получается при описанном способе выбора столбцов.
Пусть теперь и — наибольшее значение 1, для которого справедливо неравенство (4.20). Тогда существует (и, й)-код с минимальным расстоянием й, который удовлетворяет неравенству 42, Границы вероятности ошибки для блоковых кодов, используемых при передаче по двоичному симметричному каналу д Е с',Фд" ', ! !А2!+1 (4.23) поскольку п — г( компонент, в которых два слова совпадают, не могут влиять па вероятность перепутать зги слова ').
Этот результат вместе с верхней границей Элайеса для минимального расстояния позволяет получить нижнюю границу величины Р„которая является достаточно точной при малых скоростях передачи. Для любого двоичного (а, А)-кода с расстоянием, не превосходящим д, величина Р, не может быть больше, чем вероятность припять переданное слово за соседнее, умноженная на число всех кодовых слов. Эта суммарная граница может быть записана как С'!Р'!;!" '.
(4.24) ! ! л!+! Далее, если минимальное расстояние двоичного (п,й)-кода равно !(, то все комбинации из ! =!!(ч' — !)/2)нлн меньшего числа ошибок могут быть исправлены. Следовательно, вероятность правильного декодирования для наилучшего (п,й)-кода может быть ограничена снизу: Р(~ ), СРЯ ! с+! (4.25) Этот результат вместе с границей Вар!измена — Гилберта позволяет найти верхнюю границу для Р„которая достаточно точна при малых скоростях передачи. (См. задачу 4.2,) Однако можно получить значительно более точные границы, щ дг ~ ЗЛЧ вЂ” (Ы5>. С ИГ П*! б б Р ' *' ' "Р Р !з) = з. В Границы, полученные в предыдущем разделе, могут быть использованы с целью получения границ для Р, — вероятности ошибочного декодирования наилучшего двоичного кода при заданных скорости и длине передачи по двоичному симметричному каналу.
Если известно, что минимальное расстояние для двоичного кода не превосходит !г, то величина Р„ конечно, не меньше, чем вероятность спутать переданное кодовое слово с другим словом, отстоящим от кодового на расстояние д. Таким образом„ для двоичного симметричного канала будут получены две наиболее важные из них: граница сферической упаковки и граница случайного кодирования. Начнем с некоторых определений, которые потребуются.
Линейный код, совокупность образующих смежных классов которого в точности совпадает с совокупностью всех последовательностей веса 1 или меныпе для некоторого 1, называется совершенным. Код, среди образующих смежных классов которого при некотором 1 содержатся все последовательности веса 1 или меньше, часть последовательностей веса 1+ 1 и нет ни одной последовательности большего веса, называется квазисовершенньии.
Двоичный групповой код называется отимальным для двоичного симметричного канала, если его вероятность ошибки не превосходит вероятности ошибки для любого другого двоичного группового кода с тем же самым общим числом символов и таким же числом информационных символов. При установлении границы сферической упаковки для Р, используется граница Хэмминга для минимального расстояния. Предположим, что существует квазисовершеиный (п, й)-код, т.
е. такой код, что при некотором Г все векторы веса 1 или меньше являются образующими смежных классов, причем среди образующих смежных классов нет векторов, вес которых больше чем 1+!. Следующие соображения доказывают, что этот код должен быть оптимальным. Вероятность правильного декодирования может быть записана следую~ням образом: Р,=пЯ+пРЯ ' + Р О' + ..., где а; — число образующих смежных классов, вес которых равен ю'. Так как величина РЧ;1 -' уменьшается с ростом 1 (если Р ~ 9), то вероятность правильного декодирования возрастает, если увеличить одну из величин а~ и уменьшить следующую за ней величину.
(Заметим, что сц~+ си + аз+... = 2и-к есть число смежных классов.) Для квазисовершенного кода каждый нз 1 первых коэффициентов он равен числу векторов веса 1, так что каждый из этих коэффициентов принимает наибольшее возможное значение. Слагаемые, следующие за (1+ 1)-м слагаемым, равны нулю, а ам~ соответствует всем остальным смежным классам.
Поскольку а; не могут быть увеличены за счет последующих членов последовательности, то вероятность правильного декодирования имеет наибольшее возможное значение. Поэтому вероятность правильного декодирования может быть записана в виде Р, = а" + С'„Р(~" '+ фРа" + ... ... + С'„Р'Я" '+иг НР "'О" (4.26) где 1 — наибольшее целое число, удовлетворяюшее соотношению а~~,=2Я "— 1 — С„' — ф— ...
— С„' О. (4.27) Квазисозершенпые (я,й)-коды существуют не для всех значений и и й. В тех случаях, когда квазнсовершениый код не существует, вероятность правильного декодирования наилучшего кода мевьше, чем величина Р„удовлетворяющая соотношениям (4.26) и (4.27) . Теорема 4.8. Лля любого (н, й) -кода Р, )[С,~' — а~+ Д '+'Я" ' + Х С~Р~О" ', (4.28) где ! и асы определяются соотношениями (4.27). Нетрудно получить следующий простой асимптотически верный результат. Во многих случаях удобно пользоваться величиной Е, называемой надеаеностью или экснонентой ошибки 1 Е= — Вгп — [1од, Р, (для наилучшего двоичного группового кода)[. й -~ Обозначим через Е, границу сферической упаковки для надежности: Е~ (Е,= — 1пп — !оде[С,', Р' Я" + к-э.
+С'„+ Р ~зЯ ' '+ ... + С„"Р"~ = Е( —, Р), (4.29) где Е(Х, Р) — функция, определяемая в приложении А. Кроме того, из соотношения (4.27) получаем -1- !он, [ ! + С„'+ ... + СД я.. < 1 — — ~ <— 1одД! + С, + ... + С„~. (4,30) Иш [! — — „)=Н( — ). (4.31) Таким образом, при больших значениях п величина 1, входящая в соотношение (4.29), приближенно равна половине расстояния, задаваемого границей Хэмминга, нли, другими словами, расстоянию, задаваемому границей Гилберта. Можно получить несколько более точные границы, чем вышеприведенные, однако они более громоздкие; дальнейшие уточнения получены в работах [68, 69, 79, 270).
Граница для Е, задаваемая соотношениями (4.29) и (4.3!), изображена на фиг. 4.2 для Р = 10 '. Можно получить также асимптотические формулы для границ (4 23) н (4.24). (См. задачу 4.!.) В соответствии с утверждением, доказанным в приложении А, пределы при и- сс для верхней и нижней границ (4.30) совпа- дают, так что цв з 'з [!+ЛГа! *в с Верхняя граница случайного кодирования для Р„получаемая в этом разделе, справедлива только для групповых кодов, используемых при передаче по двоичному симметричному каналу; Шенноном и другими авторами были установлены более общие результаты.
При установлении этой границы используется тот факт, что иногда легче вычислить среднюю вероятность ошибки для класса кодов„чем вероятность ошибки для отдельного кода, и что в классе кодов должен существовать некоторый код со свойствами не хуже усредненных. Рассматриваемый класс кодов является подпространством пространства строк всех матриц вида [!йР4, где 1й — единичная мат- а цг ць,в о щ пь и ьхврввл!ь Фиг.
4.2. Графики границ надежности как функции скорости для блоковых кодов при передаче по двоичному симметричному каналу с Р = О,О!. А — ярямояяяейоая граякца; Б-граяяца сееркческой уоакоакя: В -граяяца саучайяого кояяроааяяя. рица размерности А Х й, а Р— матрица с двоичными элементами размерности йХ(п — й). Каждая из 2М"-м возможных матриц Р задает двоичный групповой код, хотя, вообще говоря, имеется много эквивалентных кодов с различными матрицами Р. Верхняя граница находится для средней вероятности ошибки по подмножеству, которое содержит более половины этих кодов. Разумеется, наилучший код по меньшей мере столь же хорош, как средний, поэтому, кроме того, получается верхняя граница вероятности ошибки для наилучшего кода. Начнем с вычисления числа кодов, содержащих в качестве кодового вектора фиксированный набор длины п.
Нулевой вектор есть в каждом коде. Если все А первых символов вектора ч (информационные символы) равны нулю, а остальные и — я символов (проверочные символы) не все равны нулю, то такой вектор не может быть кодовым вектором ни для какого кода. Если, однако, не все информационные символы вектора ч равны нулю, то имеется 2П'-'Х"-ю кодов, содержащих вектор ч. Этот факт может быть доказан следующим образом. Пусть некоторый вектор ч содержит среди информационных символов более чем одну единицу.
Будем прибавлять к нему строки порождающей матрицы так, чтобы в левой части среди информационных символов осталась только одна единица. Вектор ч', полученный таким образом, является кодовым вектором тогда и только тогда, когда первоначальный вектор ч был кодовым вектором. Поскольку среди его информационных символов имеется только одна единица, он должен совпадать со строкой порождающей матрицы, содержащей единицу в той же самой компоненте.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
