У. Питерсон - Коды, исправляющие ошибки (1267328), страница 25
Текст из файла (страница 25)
В работе Робинсона [256] получен более точный, хотя и более сложный вариант этого результата. Кроме того, другая верхняя граница для Н найдена в работе [334). Однако для этой границы до сих пор не найдено простого выражения и не известно ее предельное значение при и, стремящемся к бесконечности. Выражение границы Хэмминга для сверточных кодов можно получить, используя результаты следующего раздела [соотношение (4.6!Ц. Однако используемые при этом аргументы являются несколько искусственными, и проблема получения истинной границы Хэмминга для сверточных кодов остается открытой. (См.
задачу 4.10). Можно получить нижнюю границу минимального расстояния, достигаемую на некотором сверхточном (и, й)-коде. Этот результат, который справедлив также для более общего класса линейных древовидных кодов, аналогичен границе Варшамова — Гилберта для блоковых кодов [38, 185, 205, 256, 333, 334). Сверхточный код в систематической форме полностью определяется выбором матриц Рь 0 ( ! ( т — 1, размерности Ас Х Х(по — 1го) входящих в определение (3.13).
Таким образом, если символы кода выбираются из алфавита объема д, то существует д '"~м х> возможных сверточных кодов. Любой набор двины п, первый блок которого не состоит полностью из нулей, появляется в д"'<~ иы кп из этих кодов. Доказать это можно следующим образом. Рассмотрим набор длины и, среди информационных символов которого в первом блоке содержится только одна единица (любой другой набор длины и, первый блок которого не состоит целиком из нулей, может быть получен из такого набора с помощью элементарных операций над строками), и используем этот набор в качестве одной из первых й, строк матрицы О. Остальные йа — 1 из этих первых йр строк могут быть выбраны произвольно, но после этого матрица С полностью определена.
Для систематического кода каждая из этих строк содержит лг(па — А,) произвольных символов. Таким образом, т(йз — 1) (пз — /гав) символов могут выбираться произвольно, и существует д <ь "м -~> кодов, где может появиться фиксированный набор длины а, первый блок которого не является полностью нулевым.
Любой набор длины и, который, будучи кодовым словом, не содержит в качестве первого блока полностью нулевой блок, должен иметь среди Аз информационных символов первого блока по крайней мере один, отличный от нуля. Обозначим через ! число ненулевых информационных символов в первом блоке; пусть )в вес набора длины и. При фиксированной комбинации из ! символов среди первых йь компонент имеется комбинаций, которые могут появиться на месте последних п — йь компонент при условии„что общий вес набора меныпе чем !(.
Суммируя по !, получим У(д) — общее число наборов длины и, вес которых меньше чем д, содержащих по меньшей мере один ненулевой символ среди первых йь символов, т. е. Теперь определим с(а — расстояние Гилберта как наибольшее значение д, при котором )Ч(д) ( д"-х, Тогда произведение числа наборов длины п и веса, меньшего чем дз, которые содержат отличные от нуля символы среди первых йь компонент, на число кодов, в которых каждый из них может появиться, строго меньше, чем число кодов.
Следовательно, существует по меньшей мере один код с минимальным расстоянием с( или болыпе, если Ггп И-!-! Х Сь(д — ц' Х С' ь,(д — ц (д '"' '". (4.52) ! ! 1-ь В частности, существует код с минимальным расстоянием дз, где 0с — наибольшее значение д, удовлетворяющее неравенству (4.52). Если с(с — наибольшее значение с!, удовлетворяющее неравенству (4.52)„то противоположное неравенство будет справедливо, если с( заменить на Ис+ 1.
Таким образом, справедлива следукицая теорема: Теорема 4.12. Суи1естеует сверточный (тпь,тйь)-код с минимальным расстоянием, раеньич по меньисей лере с(х, причем Нетрудно показать, что, как и в случае блоковых кодов, минимальное расстояние для большей части кодов только незначительно меньше с(с. При д = 2 получается, как и для блоковых ко« дов, такое же асимптотическое выражение при а, стремящемся к бесконечности, т. е. (2) (4.54) Границы для минимального расстояния в этом разделе получены для систематических сверточных кодов.
Любой несистематический код с длиной кодового ограничения и эквивалентен систематическому коду с такой же длиной кодового ограничении, и поэтому эти границы справедливы для всех сверточных кодов. Соотношения (4.22) и (4.54) наводят на мысль, что при больших значениях п разность между минимальными расстояниями наилучших блокового и сверточного кодов относительно мала. При малых значениях п наилучшие границы величины И для сверточных кодов несколько выше, чем соответствующие результаты для блоковых кодов.
По-видимому, это означает, что при заданных значениях и и й сверточные коды имеют несколько большее минимальное расстояние. Наилучшие известные коды, рассматриваемые в гл. 5, !О и 13, подтверждают это. 4.5. Границы вероятности ошибки для сверточных кодов, используемых при передаче по двоичному симметричному каналу В предположении, что не происходит неограниченного или катастрофического нарастания ошибок, следует ожидать, что прн больших значениях ( величина Р,(0( — ~) хорошо аппроксимируется Для блоковых кодов, используемых в канале без памяти, результаты последовательного декодирования являются независимыми.
Поэтому определение вероятности ошибочного декодирования Р, в принципе довольно просто. Однако для сверточных кодов ситуация оказывается существенно другой, поскольку вероятность ошибочного декодирования фиксированного блока в значительной степени зависит от результатов декодирования предшествующих блоков. Другими словами, величина Р, для фиксированного блока может изменяться из-за ошибок в канале, которые появлялись в любой момент времени в прошлом. Пусть через Р,( — () обозначена вероятность того, что последняя ошибка появилась в ( — Ц-м блоке„ а через Р,(0~ — г) обозначена условная вероятность неправильного декодирования нулевого блока при условии, что ( †()-й блок был декодирован неправильно.
Тогда вероятность ошибочного декодирования нулевого блока Р, = ~', Р, (О ~ — () Р, ( — (). величиной Р,,— вероятностью ошибки для первого переданного блока. Если можно предположить, что эта аппроксимация справедлива при всех значениях 1, получаем Ре Р1е Х Ре( 1) Р1е (4.55) а 1 Величина Ра, может быть легко вычислена и при перечисленных выше предположениях может быть использована как приближенное значение вероятности ошибки. Заметим, что если вероятность ошибки в канале мала, то каждый коэффипиент Р,( — 1) в соотношениях (4.55) также будет мал, и поэтому отличие Р, от Ра е будет незначительным.
В любом случае величина Р,, является некоторой оценкой надежности для сверточных кодов, н в некоторых ситуациях лучших оценок получить не удается. В дальнейшем используются обе величины: Р, и Ра,. Для конкретного сверточного кода вероятность первой ошибки в принципе может быть вычислена непосредственно. Если пользоваться стандартным расположением, то величина Р„равна сумме вероятностей наборов длины и, входящих в подмножества с номерами от 2 до 2ь, т.
е. в неправильные подмножества. Так же как и для блоковых кодов, громоздкость стандартного расположения обычно делает невозможной любую процедуру, связанную с перечислением. Для сверточных кодов может быть получена наиболее важная из границ — граница случайного кодирования. Ее вывод аналогичен выводу для случая блоковых кодов. Однако теперь рассматриваемые коды образуют пространства строк матриц вида (3. 13): -1Р, ОР, ...
ОР 1ро ° .. Оре — х При установлении границы Гилберта было показано, что существует 2 ь'"' ~~ способов выбора матриц Рь 0(1(т — 1, и поэтому в этом классе столько же кодов. Кроме того, было показано, что любой набор длины и с ненулевым первым блоком может быть кодовым словом не более чем в 2 ' ' " "' л кодах. Пусть 1( определяется так же, как и в неравенстве (4.32), т. е. е(х — наибольшее целое число, такое, что а -1 ( числа наборов длины и 2" ь-~2 ~ Са, 1 с ненулевым первым блоком, . (4.56) а-о " ~ вес которых меньше дк ! Таким образом, число кодовых слов с ненулевым первым блоком, вес которых меньше чем 0а, во всех кодах ограничено сверху: нз-1 2их(м — им~ — зл ~ С~ 2~ ~ ~ а' '0 0<~1 < Я Ф())=0, 1+~ у (и < 2т (Вв — н (ла — ьв ~ 1 ~ ~ Сы+1-и/2С(а+г — 1)д ))- ю-l ! 8 Йз-1 а=аз )г'Ц) = общего числа кодов с Н > йз, йа~(1.
Ц<) <с~а (4.57) Далее, вероятность каждой комбинации из 1 ошибок равна Рг~"->, и имеется всего С„таких комбинаций. Суммируя по ), Следовательно, менее половины сверточных кодов могут содержать наборы длины п с ненулевым первым блоком, вес которых меньше дз. Другими словами, теорема 4.9 справедлива как для блоковых, так и для сверточных кодов. При больших значениях и разность между величиной дз, которая определяется неравенствами (4.56), и расстоянием Гилберта, использованным в теореме 4.12, пренебрежимо мала.
Таким образом, можно сказать, что минимальное расстояние для большей части сверточных кодов по меньшей мере близко к расстоянию Гилберта. Теперь, так же как и прежде, необходимо оценить сверху число кодов с минимальным расстоянием и' ) г(з, для которых появление комбйнации ошибок веса ) приводит к неправильному декодированию. Ошибка декодирования появляется при любом коде, в котором некоторое кодовое слово с ненулевым первым блоком лежит на расстоянии ) или меньше от полученного набора длины и.
Далее, число наборов длины и и веса г(з или больше с ненулевым первым блоком, которые отстоят от полученного набора длины п на расстояние, не превосходящее ), строго меньше, чем число наборов длины и и веса г(з или больше, которые отстоят от полученного набора длины и на расстояние, не превосходящее ). Последнее число наборов найдено при выводе соотношений (4.33). Умножая зту верхнюю границу числа возможных кодовых слов, находящихся на расстоянии ) или меньше от полученной последо. вательности, на 2 ' ' ' ~" ' — число кодов, в которых может появиться некоторое кодовое слово, — получаем верхнюю границу для )У()) — числа кодов, для которых комбинация ошибок веса ) приводит к первой ошибке декодирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
