У. Питерсон - Коды, исправляющие ошибки (1267328), страница 20
Текст из файла (страница 20)
(Это коды Голея, описанные в равд. 5.2.) (Указание: воспользуйтесь равенством (3.28).) 3.22. Для кодов Хэмминга, которые рассматриваются в равд. 5.1, л =(Ч вЂ” 1)/(9 — 1), й = и — гл, и все векторы нулевого пространства обладают одним н тем же весом. (См. задачу 3.5.) Покажите, что для кодов Хэмминга и А(Х)= ~ А;Х'= ю-о = — '((1+(д — 1)Х)" +(4 — Ц(1+(д — 1)Х!! — и (1 — Л)' ').
Найдите числа А; для двоичного (7,4)-кода. 3.23. Покажите, что если столбцы порождающей матрицы б двоичного кода представля!от собой все 2ь-' ненулевые наборы длины й, то все кодовые слова являются словами веса 2"-'. 3.24. Покажите, что если столбцы порождающей матрицы б д-ичного кода представляют собой все 4ь — 1 ненулевые наборы длины й, то все кодовые слова являются словами веса (д — 1) 4х-'. 3.25. Покажите, что если столбцы порождающей матрицы кода б представляют собой (д" — !)/(д — !) векторов, ни один из которых не пропорционален никакому другому, то все кодовые векторы являются словами веса дь-'. (Указание: используйте результаты двух предыдущих задач.) 1 Возможности исправления ошибок с помощью линейных кодов Очень важно знать предельные возможности кодов, исправляющих ошибки, и накладываемые ими ограничения.
Эта информация н знание того, что практически достижимо, позволяют судить о том„ какие проблемы в принципе разрешимы и какие требуют дальнейшей разработки. Кроме того, на ранней стадии построения системы связи полезно иметь оценки характеристик кодов, которые дают возможность довольно просто оценивать относительную эффективность различных кодов.
В разд 4.1 получены верхняя и нижняя границы минимального расстояния для линейных блоковых кодов при фиксированных длине и скорости. В равд. 4.2 определяются границы для вероятности ошибочного декодирования в случае наилучшего линейного блокового кода, используемого при передаче по двоичному симметричному каналу. Значение этих границ обсуждается в равд.
4.3. В разд. 4.4 и 4.5 получены соответствующие границы длч сверточных кодов. В последнем разделе приведены границы для блоковых и сверточных кодов, исправляющих пакеты ошибок. 4.!. Границы минимального расстояния для блоковых кодов В случае линейного кода при фиксированных значениях а и А можно получить верхнюю н нижнюю границы для наибольшего минимального расстояния. Нижние границы, конечно, справедливы и для более широкого класса кодов, поскольку они просто устанавливают то, чего можно достичь; верхяие границы могут быть получены также для нелинейных кодов, но здесь это не делается.
Верхняя граница Плоткина устанавливает довольно грубую границу для й. Лемма 4.1. Минимальный вес кодового слова в линейном (п, й)-коде равен самое большее пах '(4 — 1)!(Чь — 1). Доказательство. Сумма весов кодовых слов линейного (и, А)* кода с символами, взятыми из поля с д элементами, равна ать '(4 — 1). (См. задачу 3.6.) Утверждение леммы вытекает нз того, что общее число элементов с ненулевым весом равно дь — 1 н ми минимальный вес элемента не может превышать средний вес. Ч.
т, д. и усть В(п, й) — максимально возможное число кодовых слов линей йного кода длины я е минимальным весом, не меньшим й. Лемма 4.2. Если и И, то В(п,с() <дВ(п — 1, Н). Доказательство. Пусть 6 — код с и символами и минимальным весом, не меньшим И, содержащий В(п, с() кодовых слов. Совокупность Р всех кодовых слов из 6, последним символом в которых является нуль, образует надпространство пространства 6, поскольку сумма любых двух элементов из Р и любое произведение элемента из Р на скаляр принадлежат Р. Можно образовать д смежных классов в пространстве 6 по подпространству Р так, что каждому значению символа, который может появиться на месте последней компоненты, соответствует один из смежных классов; таким образом, 1/д-я часть всех элементов из 6 входит в Е.
Поэтому подгруппа Е образует линейный код с (1/д) В(п,г() кодовыми словами и минимальным весом, по крайней мере с(, причем последняя компонента каждого из векторов этого кода равняется нулю. Если отбросить эту компоненту, то получится линейный код с п — 1 символами и с тем же самым числом кодовых слов и весом.
Может оказаться, что в полученном коде Р найдутся другие столбцы, состоящие из одних нулей. Однако каждый из них можно заменить столбцом любого другого типа, вследствие чего минимальный вес кода не уменьшится. (Заметим, что В(п — 1, и — 1) =д, соответствующий код состоит из и — 1 повторений одного и того же информационного символа. Таким образом, при условии и) г( в коде из п — 1 символов возможны ненулевые столбцы.) Следовательно, В(п — 1, Н) <(1/д) В(п, й). Ч.
т. д. Лемма 4.1 применительно к коду длины 1 может быть переписана в виде 1( ~ь 1) (/дь-! (д !) да-'(д1/+1 — /д) (Н, и если дд+ ~ — /д) О, то (4.2) д~ В(1, Н) < +д,. (4.1) Выберем теперь 1 так, чтобы (дН вЂ” !)/(д — 1) =1+/, где 1 — целое число и О / < 1; тогда дИ ) ~ ча — (д — 1) 1 1 + (д — 1) / ' Если и ~ й то, повторно применяя лемму 4.2, получаем и- 1МЛ- ШМ- Ъ)1+ $д,~ Вь,л(с-'ВР,4(~ — т — — — — -~~.
(43> Можно показать, что дг< 1+(д — !)/, и, следовательно, В(п, ()==д--«л-'»М- д/. (4.4) 0 Ц1 0,155 0,2 ЦЗ Ц4 Ц5 Минимальнее россп следе/2п Фнт. 4Л. Границы для минимального расстояния наилучшего двоичного блокояого кода (длина кода я предполяга«тся очень большой). А — верхняя границе Плотнинв; и — верхняя граница Хвммингв, "В-верхняя граница Элвйесвр à — нижняя граница Вяржвмове — Гилберта.
Поскольку для кода с наибольшим минимальным расстоянием В(п, й) = ой, где й — число информационных символов этого кода, то ь<п Ч ! + 1+!ожег й. Таким образом, верна следующая теорема; Теорема 4.1. Если п~ (ой — !)Дд — 1), то число проверочных сшиволов, необходимое для того, чтобы минимальный вес линейного блокового кода с п сшяволами достигал значения й, равно самое меньшее Цдй — 1)/(д — 1)) — ! — 1осг й. Если й очень велико, то последними двумя слагаемыми в этом выражении можно пренебречь. Эта асимптотическая граница по~азана на фиг.
4.1 для двоичного случая, Граница Плоткина может быть получена также для нелинейных кодов. Теоремы 4.2, 4.3 и 4.4 посвящены уточнению этой границы. Теорема 4.2. Если существует (и, Ь)-код над бр(д) с минимальным расстоянием д, то существует (и — д,й — 1)-код с минимальным расстоянием самое меньшее д/д. Доказательство. Расположим все кодовые векторы в виде матрицы, первой строкой которой является нулевой вектор, второй строкой — вектор чь веса д, а затем следуют векторы, получаемые умножением вектора чь на элементы поля. Затем переставим столбцы так, чтобы в первых и — д столбцах были нулевые компоненты вектора чь и векторов, кратных чм а последние д столбцов содержали их ненулевые компоненты.
Эти первые д векторов образуют надпространство„ а весь код состоит из дь-' смежных классов по этому подпространству. В каждом смежном классе первые п — д компонент равны. Таким образом, если отбросить последние д компонент каждого вектора, то оставшиеся векторы, содержащие н — д компонент, будут представлять собой д раз повторенное подпространство размерности Ь вЂ” 1 наборов длины а — д. Покажем теперь, что минимальное расстояние этого надпространства равно самое меньшее д/д.
Пусть ч,— некоторый вектор первоначального кода, который не может быть получек из чь умножением на элемент поля, и пусть вектор ч, содержит а, ненулевых компонент среди своих первых а — с( компонент и аз ненулевых компонент среди своих последних д компонент.
Тогда, поскольку минимальный вес в первоначальном коде равен д, то а, +аз)д. (4.6) Обозначим через Ьи 1= 2, 3, ..., д, число ненулевых компонент вектора чь которые совпадают с соответствующими компонентами Ьго кодового слова среди д — 1 ненулевых кодовых слов, полученных умножением на элементы поля вектора чь, Тогда, поскольку каждая из аз ненулевых компонент вектора ч~ совпадает с компонентой одного произведения вектора чь на скаляр, то (4.7) Ь,= 2 Итак, среднее значение чисел Ь; равно аз/(д — 1), и по крайней мере одно из чисел Ь; должно быть не меньше среднего.
Поэтому должен существовать кодовый вектор, представляющий собой произведение вектора чь на некоторый элемент поля, например рчь содержащий среди последних д компонент Ь|~ ах/(д — 1) компонент, которые совпадают с соответствующими компонентами вектора чь Таким образом, вектор ч1 — рва является кодовым сло- вом, содержа!цим а1+ с! — Ь! ненулевых компонент. Итак, а,+д — Ь,= д, или а~ — Ь;)О, или или да,~~а, +ам Поэтому из неравенства (4.б) следует, что уа! ) б, или а,) —, з (4.8) Ио а, †в произвольного вектора из (и — д, й — 1)-кода, полученного отбрасыванием последних д компонент каждого кодового вектора.
Ч. т. д. Теорема 4.3. Наименьшее значение и, для которого существует (и, й)-код с минимальным расстоянием д, удовлетворяет неравен- ству с-и (4.9) где щь-' — наименьшее целое число, кратное чь-', которое болыие или равно д, и т-а здь-' — д= Х бд!, О~б,- <д; (4.10) ~ ь ч — 1 В и)— д — ! — (дю+! !)— ю ь ч — ! ь ч — 1 (4.1 1) Это неравенство справедливо, так как (А, Ь)-код, содержа!ций все наборы длины Ь, является кодом с минимальным расстоянием, рав- ным !.
таким образом, б; — зто разряды числа здь — ' — д в системе счисления с основанием д. Доказательство. Доказательство проводится индукцней по А Если с(=1, то з=! и все б; равны д — !. Тогда неравенство (4.9) принимает вид Предположим теперь, что утверждение теоремы справедливо для любого значения т(, меньшего 4~ По теореме 4.2, если сушествует (и, А)-код с минимальным расстоянием с(м то существует (и — (/о. й — 1)-код с расстоянием, не меньшим йь где А — наименьшее целое число, большее или равное дэ/д.
По предположению индукции справедливо соотношение (4.9), которое и дает границу для и — с(о. Если ь -э '!о= з4 е бн/ ° ~-о то х-2 Ф-1 л но»~ ч — ! 'ч — !' а ! так что п~~(п г/с)+г!0= +ад» ~ ~ б~ 1 ! х ! гы эд — ! Ч~,', 4 ;-о ю О Ч. т. д. Для порождаюшей матрицы 6» столбцами которой являются (4х — 1)/(д — 1) наборов длины й, ни один из которых не пропорционален другому, все ненулевые кодовые слова имеют вес, равный д" — '. Можно построить (з(д" — !)/(д — 1),й)-код, все ненулевые кодовые слова которого имеют вес, равный э4" '.
В качестве порождающей матрицы этого кода 6, можно выбрать, например, матрицу, состояшую из з повторений матрицы Сь На этих кодах достигается граница, задаваемая теоремой 4.3. Путем отбрасывания части столбцов из б, могут быть построены дополнительные коды. Для любого !(А рассмотрим матрицу, получаюшуюся из матрицы Сь если выбрать в матрице б, ! линейно независимых столбцов и все столбцы, которые являются линейными комбинациями этих ! выбранных столбцов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
