У. Питерсон - Коды, исправляющие ошибки (1267328), страница 24
Текст из файла (страница 24)
задачу 4.!), вытекает, что при Я = О надежность ограничена также и сверху величиной '~, !од (! ~.ь|4РО). Таким образом, при 11 = О надежность наилучшего кода точно известна. Этот факт был использован П1енноном, Галлагером и Берле- кэмпом (272) при получении другой границы, которая равномерно лучше, чем граница (4.23). Вывод этой прямолинейной верхней границы надежности связан с понятиями, нигде больше в этой книге не используемыми, и поэтому опускается.
Сама эта граница показывает, что кривая зависимости надежности от скорости передачи для последовательности наилучших кодов не может лежать выше прямой линии, являющейся касательной к границе сферической упаковки и проходящей через известную точку нулевой скорости. Эта граница также изображена на фиг. 4.2. 4.3. Обсуждение границ для блоковых кодов Полученные верхние и нижние границы могут интерпретироваться как границы для значений минимального расстояния 4 возможного для (и, й)-кода. Если отношение А/и остается постоянным, а а стремится к бесконечности, то в пределе границы для отношения г(/и становятся фиксированными постоянными величинами, не зависящими от и.
Эти границы изображены на фиг. 4.!. На кодах Хэмминга и в случае болыпих скоростей передачи на эквивалентных кодах Рида — Маллера и кодах Боуза — Чоудхури — Хоквингема (БЧХ-кодах), рассматриваемых в следующих главах, достигается граница Хэмминга, и они являются оптимальными. На кодах из теоремы 4.6, кодах Рида — Маллера и БЧХ-кодах для малых скоростей передачи достигается граница Плоткина. Следовательно, все эти коды имеют наибольшее возможное минимальное расстояние.
Тем не менее при больших значениях и скорости передачи для всех этих кодов стремятся либо к нулю, либо к единице. В области средних скоростей передачи как для БЧХ-кодов, так и для мажоритарных кодов, рассматриваемых в гл. 10 и 11, при любой фиксированной ненулевой скорости передачи отношение д/и стремится к нулю, когда и неограниченно возрастает. На БЧХ-кодах, однако, все еще приблизительно достигается граница Варшамова — Гилберта при п = 1023.
Системы кодирования, для которых было бы доказано, что отношение д/и остается конечным, когда и неограниченно возрастет, а отношение й/п остается фиксированным не известны, хотя граница Варшамова— Гилберта показывает, что такие 'коды существуют. Однако теорема 4.9 утверждает, что ббльшая часть кодов обладает этим свойством. Теперь рассмотрим коды для двоичного симметричного канала. Из основной теоремы Шеннона для канала с шумом следует, что при любой скорости й/и, меньшей чем пропускная способность канала, существуют коды, вероятность ошибки для которых произвольно мала. В настоящее время известны только две системы неслучайного кодирования, а именно безошибочное кодирование Элайеса (равд. 5.8) и каскадные БЧХ-коды Форин (равд.
5.!О), для которых достижимая вероятность ошибки приближается к нулю, а скорость передачи не стремится к нулю, когда длина кода и возрастает. Имеется еще один заслуживающий внимания факт, Число ошибок, появившихся в блоке из и символов при передаче по двоичному симметричному каналу, имеет биномиальное распределение вероятностей со средним значением пР и стандартным отклонением АР~~. Доля ошибочно переданных символов имеет поэтому среднее значение Р и стандартное отклонение )/Р~)/и. Когда п неограниченно возрастает, то стандартное отклонение стремится к нулю, и при фиксированном значении Р, ) Р вероятность того, что произойдет Рзп или больше ошибок, стремится к нулю. С другой стороны, если Р, ( Р, то вероятность того, что произойдет Р,п или больше ошибок, очевидно, не стремится к нулю.
Код с минимальным расстоянием д и с декодировияием в пределах кодового Расстояния исправляет все комбинации ошибок веса 1 =((д — 1)/2) или меньше и не исправляет никаких других комбинаций ошибок. Если 1= пР„то вероятность ошибки стремится к нулю при возРастании п тогда и только тогда, когда Ро ) Р. Скорость передачи для такого кода в соответствии с границей Злайеса ограничена величиной, меньшей чем пропускная способность канала, хотя при Р ( 1О ' эта разница совсем мала. (См. задачу 4.4.) Другими словами, для реализации пропускной способности канала система кодирования должна обладать способностью исправлять ббльшию часть комбинаций ошибок веса, несколько большего чем ((а — 1)/2); исправление всех комбинаций ошибок гарантируется только для комбинаций веса ((й — 1)/2).
Таким образом, хотя лучшие известные в настоящее время коды являются очень полезными для практического использования, они значительно хуже теоретически возможных пределов, и, несомненно, было бы очень интересно с теоретической точки зрения найти явные способы построения кодов, обладающих по крайней мере теми свойствами, на существование которых указывают найденные границы, или показать, что такие построения невозможны. Будут ли эти коды представлять практический интерес, зависит от того, насколько реально создание оборудования для их практического использования. Относительно теоретических пределов сложности декодирования или количества вычислений, необходимых при декодировании в случае блоковых кодов, имеется мало сведений (2661 4.4. Границы минимального расстояния для сверточиых кодов Результаты этого раздела показывают, какие значения минимального расстояния достижимы н какие не достижимы для евер.
точных (п,й)-кодов. Получены границы, аналогичные границам Варшамова — Гилберта и Плоткина для блоковых кодов, и показано, что при болыпих значениях п они совпадают. Верхняя граница наибольшего минимального расстояния (256) систематических сверточных кодов аналогична границе Плоткина для блоковых кодов. Проверочную матрицу Н сверточного (тпь, птйь)-кода с минимальным расстоянием й можно рассматривать как проверочную матрицу линейного блокового кода такой же длины с тем же количеством информационных символов. Конечно, полученный таким образом блоковый код не будет систематическим блоковым кодом, но будет эквивалентен одному из таких кодов. «Укоротим» этот код, полагая равными нулю й — Ль информационных символов (соответствующих й — йь правым столбцам матрицы Н).
Получившийся новый код имеет такое же число проверочных символов, что и исходный код, и только йь информационных символов. Кодовые слова нового кода образуют подмножество множества кодовых слов исходного кода, откуда следует, что минимальное расстояние нового блокового кода йь не меньше, чем минимальное расстояние исходного блокового кода. По той же причине й,— вес кодового слова, не все первые пь компонент которого нулевые, равен по меньшей мере а. Таким образом, (4.46) С другой стороны, можно доказать, что с(ьХ с(ь + [ ь ~ (пь йь).
(4.47) Предположим, что кодовое слово минимального веса йь содержит первый ненулевой символ в 1-и блоке длины пь. Если 1= 1, то д,= аь и справедливо соотношение (4.47). Из формы матрицы Н видно, что при 1= 2 должно существовать кодовое слово, первый ненулевой символ которого принадлежит первому блоку и вес которого равен аь+ (пь — нь) или меньше. Это слово соответствует исходному слову, сдвинутому влево на один блок, за исключением последних пь — йь проверочных символов, среди которых может находиться самое большее пь — Аь ненулевых символов.
Вообще должно существовать кодовое слово веса йь+(1 — 1) (пь — йь) или меньше с ненулевым первым блоком. Но поскольку имеется только йь информационных символов, то 1 должно быть меньше или равно наименыпему пелому числу, которое больше или равно йь/йь. (4.48) йь=[, 1 ~ — (па — нь) пь+ 1 ° (4.49) Используя соотношения (4.46), (4.47) и (4.49) и теорему 4.1 и замечая, что любой сверточнын код эквивалентен некоторому систематическому коду, получаем следующий результат: Теорема 4.11.
Минимальное расстояние сверточного (тппь,гпйь)- кода с длиной кодового огРаниченил п = тпь УдовлетвоРлет не- равенству Ц'"' '~-.( — 11 й~й,+(,— й,)) ' ' „~, (4.89) где дь — наибольшее целое число 1, такое, что Ф вЂ” 1 1овы(~ ~ьп (по нь) Отсюда непосредственно следует соотношение (4.47), Теперь величину йь можно оценить сверху, пользуясь границей Плоткина для блоковых кодов, даваемой теоремой 4.1.
Оценка получается наиболее точной, если йь выбирать настолько малым, насколько это возможно. Для того чтобы была применима теорема 4.1, величина йь+ гп(пь — йь) должна быть равна самое меньшее (ь7ь(ь — !)!(ь( — 1), поэтому выберем При больших значениях а и д =2 соотношение (4.50) принимает форму Д( —, (4.51) что совпадает с соответствующим результатом для блоковых кодов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
