У. Питерсон - Коды, исправляющие ошибки (1267328), страница 28
Текст из файла (страница 28)
Укорачивая первоначальный код до г — 1 блоков, всегда получаем код по крайней мере с 2гпе — (г — 1)(пе — йе) проверочными символами, причем величина Ьь характеризующая способность этого кода исправлять пакеты ошибок, ограничена сверху числом гпь Ч. т. д. Этот результат может быть использован при определении верхней границы для величины Ь, характеризующей корректирующую способность сверточяого кода для пакетов ошибок. Из теоремы 4.18 получается верхняя граница для Ьи — величины, характеризующей корректирующую способность кода для пакетов ошибок, содержащихся в (Ьа/пе] блоках; обозначим эту границу через Б,.
Тогда Ь~~Ь + (4.66) Действительно, если бы величина Ь могла принимать большие значения, то это означало бы, что Ьа Бь что противоречит утверждению теоремы 4.18. Комбинируя соотношение (4.66) и теорему 4.18, получаем следующую теорему: Теорема 4.19. Величина Ь, характезирующая корректирующую способность сверточного (тпе, тйе) -кода для пакетов ошибок, ограничена сверху: п — А) [~' '~(Ь+ 1 — пе) + пе — йе (4.6?) Кроме того, очевидно, всегда верно, что Ь(~ — "-, '~. (4.68) Нет необходимости доказывать для сверточных кодов результат, аналогичный теореме 4.17. Сверточные коды, обладающие хорошей способностью исправлять пакеты ошибок, можно строить, используя методы, изложенные в гл.
14. При больших значениях и эти коды и утверждение теоремы 4.16 в совокупности показывают, что величина (и — Й)/(! + Й) является практически достижимым максимумом для сверточных кодов. Поскольку скорость передачи 1? всегда меньше единицы, то при заданных (больших) значениях и и й сверточныс коды обладают лучшей корректирующей способностью для пакетов ошибок, чем блоковые коды. Однако, по-видимому, при малых значениях и верно противоположное утверждение. Замечания Граница Плоткина взята из работы (2421, а ее улучшенный вариант — теорема 4.1 — принадлежит Элайесу.
Граянца Варшамова — Гилберта была найдена Варшамовым 1346!. Она представляет собой уточнение границы Гилберта (105) и была также найдена Саксом (263). Здесь использовано ввиду его простоты доказательство Сакса. Уточнение этой границы — теорема 4.3 — получено Грейсмером (129), а коды, на которых достигается эта граница, были найдены Макдональдом (192) и Соломоном и Стиффлером (285), Граница Хэмминга появилась в работе Хэмминга (138), а уточнение ее — в работе Уокса (320).
Границы для двоичного симметричного канала были впервые опубликованы в работах Элайеса (68, 69) и основывались на фундаментальной работе Шеннона (273). Границы вероятности ошибки для более общих каналов составляют важную часть книги Галла- гера (103); результаты и доказательства„приведенные в этой книге, включают уточнения, предложенные Галлагером. Теорема 4.9 и ее обращение получены Пирсом (238). Граница Гилберта для сверточных кодов была впервые установлена Возенкрафтом и Рейффеном (333). Было предложено несколько уточнений этой границы, однако ни одно из них не улучшило ее асимптотической формы.
Граница типа границы Плоткина для этих кодов получена Робинсоном (256). Верхняя граница для минимального рассеяния, найденная Вайнером и Эшом (334], в некоторых случаях является наиболее точной из известных границ, однако асимптотическая форма для этой границы до сих пор не получена. Идея использования границ блоковых кодов для получения аналогичных границ сверточных кодов принадлежит Витерби (312). Границы для обнаружения и исправления пакетов ошибок— результаты, эквивалентные теореме 4.15,— приведены в работе Рейгера (252). Они аналогичны некоторым результатам Файра (84).
Теорема 4.16 опубликована в работе Файра, теорема 4.17 доказана Кампопиано. Теоремы 4.18 и 4.19 были впервые доказаны Вайнером и Эшом [33 Ц. Задачи 4.1. Используя результаты приложения А, найдите асимптотическне выражения для границ (4.23) и (4.24) прн и-ьсо. Результаты сравните с другими асимптотическими границами для Р„изображенными на фиг. 4.2, 4.2.
Выведите и изобразите графически нижнюю границу для надежности при Р = 1О-', используя неравенство (4.25). Это нижняя граница надехгности для наилучшего кода, дгкодиругмого в пределах кодового расстояния (т. е. когда в любом слове может быть исправлено только (с(/2) или меньшее число ошибок). 4.3. Используя верхнюю границу Элайеса для отношения д((п, покажите, что для наилучшего кода, декодируемого в пределах кодового расстояния (задача 4.1), надежность меньше чем Е(?„(1 — Х),Р), где Н(Х) = 1 — К, 4.4, Найдите выражения для верхней и нижней границ пропускной способности двоичного симметричного канала при условии, что используется декодирование в пределах кодового расстояния.
Изобразите их графически и сравните с истинной пропускной способностью канала (выражение (4.39Ц. (Указание: определите значения 1?, при которых границы в задачах 4.1, 4.2 и 4.3 равны нулю.) 4.5. Покажите, что для линейного блокового кода длины а наличие Ь проверочных символов является необходимым и достаточным условием для исправления всех пакетов стираний длины Ь или меньше.
4.6. Определите )т', число систематических (и, А)-кодов. Найдите верхнюю границу числа систематических кодов, в которых фиксированный набор длины и может быть кодовым словом; обозначьте ее через М. Пусть 7 обозначает число ненулевых наборов длины и, вес которых меньше чем дз, а дх выбрано настолько большим, насколько это возможно для того, чтобы выполнялось неравенство УМ с Ж.
Очевидно, должен существовать по меньшей мере один код с ненулевыми кодовыми словами веса, меньшего чем д . Используя этот результат и рассматривая большие значения и, получите асимптотическую нижнюю границу для г(з/и и покажите, что она совпадает с границей Гилберта. 4.7. Пусть п = 100 и Х = 0,6. Вычислите верхнюю и нижнюю л хю т г границы для С„и 7„С„, используя результаты приложения А.
ь.=7а 4.8. Односторонняя система связи требует двоичного блокового кода с )г =0,5. Можно ли построить декодер, способный исправлять только одиночные ошибки или все одиночные и двоичные ошибки? Постройте коды для этой системы. Г1очему следует стараться сделать каждый код возможно более коротким? 4З. Сравните вероятности неправильного декодирования при передаче по двоичному симметричному каналу для приводимых ниже кодов при 10-4 ( Р ( 1. Используйте декодирование в пределах кодового расстояния. а) (23,12)-код, 1 = 3 (код Голея); б) (57,30)-код, 1= 5 (укороченный БЧХ (63,36)-код).
Обсудите случай, когда Р близко к 10-'. 4.10. Используя нижнюю границу вероятности ошибочного декодирования блока для сверточиых кодов, содержащуюся в соотношениях (4.62) и (4.63), найдите верхнюю границу для минимального расстояния. о Важные линейные блоковые коды Самые важные линейные блоковые коды — циклические коды— не обсуждаются в этой главе; нм посвящены главы 5- — 11. Здесь рассматриваются различные классы нециклнческих блоковых кодов. Некоторые из них, в том числе коды Хэмминга, Голея, Рида— Маллера н некоторые коды-произведения, эквивалентны циклическим кодам и обсуждаются также в последующих главах.
5.1. Коды Хзммннга Двоичный код Хзмминга удобнее всего задавать при помощи его проверочной матрицы. Рассмотрим матрицу Н из нулей н единиц, содержащую п1 строк и 2~ — ! столбцов, причем столбцами являются все ненулевые двоичные наборы длины и.
Над полем из двух элементов любые два вектора, дающие в сумме О, должны совпадать. Поэтому сумма любых двух столбцов из этой матрицы не равна О, и поскольку единственным отличным от нуля скаляром является 1, то не существует ни одной нулевой линейной комбинации из двух столбцов матрицы Н. Следовательно, нулевое пространство этой матрицы имеет минимальный вес, равный 3, и является кодом, исправляющим все одиночные ошибки. Длина кодовых векторов равна 2 — 1, число проверочных символов составляет пт, и, следовательно, число информационных символов равно 2 — 1 — т. Поскольку все 2" — 1 векторов, задающих одиночные ошибки, принадлежат различным смежным классам, то этими смежными классами и кодовым пространством исчерпываются все 2 смежных классов.
Поэтому образующими смежных классов для этого кода являются нулевой вектор и все векторы одиночных ошибок, причем других векторов среди образующих нет, так что код Хэмминга является примером совершенного кода. Можно построить код Хэмминга любой длины и, если выбрать матрицу Н для наименьшего значения ги, удовлетворяющего условию 2' — 1'= п, а затем просто отбросить все лишние столбцы, оставив п столбцов. Независимо от того, какие именно столбцы отбрасываются, минимальный вес кода будет все еще равен 3. Можно выбрать столбцы таким образом, чтобы получился квазисовершенный код.
(См. задачи 5.1 и 5.3.) Итак, для любого и существует код Хэммннга, исправляющий все одиночные ошибки, который является оптимальным для двоичного симметричного канала. Предположим, что передавался кодовый вектор и и появилась одна ошибка. Тогда будет получен вектор и+е, где е--вектор, содержащий 1 в том разряде, где произошла ошибка, и 0 во всех остальных разрядах. Синдром равен (и ! е)Нг нНг ! еНт еНг так как и — кодовый вектор и поэтому принадлежит нулевому пространству матрицы Н. Но поскольку е — вектор, содержащий единственную единицу в разряде, соответствующем ошибке, то синдром ейт равен как раз той строке матрицы Нт, которая соответствует ошибке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
