У. Питерсон - Коды, исправляющие ошибки (1267328), страница 23
Текст из файла (страница 23)
Остальные й — 1 строк порождающей матрицы произвольны, но после того, как они выбраны, эта строка полностью определяется условием, что вектор ч должен быть кодовым вектором. Таким образом, (А — 1) (п — А) элементов матрицы Р могут быть выбраны произвольно, н можно построить 2(ь-чх — м кодов, содержащих вектор ч в качестве кодового вектора. Итак, любой ненулевой вектор появляется не более чем в 2п'-ж -ю кодах. Обозначим через д наибольшее целое число, удовлетворяющее при заданных значениях а и й условию (4.32) с 0 Тогда общее число ненулевых кодовых слов, вес которых меньше, чем с(з, во всех кодах меньше, чем Поскольку число векторов веса, меньшего чем йз, составляет менее половины числа кодов, то справедливо следующее утверждение: Теорема 4.9. Минимальное кодовое расстояние больгией части (более половины) двоичных линейных кодов равно по меныией мере йз, где йл определяется неравенстволг (4.32).
Можно показать, что когда п возрастает при фиксированном отношении Цп, то йз/и приближается к отношениго расстояния Гилберта к длине кода. (См. теорему 4.7.) Таким образом, можно сказать, что минимальное расстояние большей части двоичных линейных блоковых кодов по меньшей мере очень близко к расстоянию Гилберта. Можно также показать, что лишь для очень небольшого числа кодов минимальное расстояние может сколько- нибудь значительно превосходить эту величину [238]. Теперь найдем верхнюю границу средней вероятности ошибки для класса всех кодов с минимальным расстоянием, равным по меньшей мере йз').
Для этого необходимо вычислить или по крайней мере оценить сверху И(/) — число кодов, при которых появляется комбинация ошибок веса ], приводящая к ошибке декодирования. Без.ограничения общности можно предположить, что передавалось слово, состоящее из нулей, и при передаче появилось ] ошибок. Ошибка декодирования получается при любом коде, в котором ненулевое кодовое слово находится па расстоянии / или меньшем от полученного набора длины и.
При этом возможны три случая. Если ] ( [йз/2], то ошибка не появится ни при каком из кодов, т. е. (4.33а) У(]) =О. Если Щ2](!~йк, то нужно вычислить число наборов длины п., которые приводят к ошибке декодирования. Поскольку каждый набор длины л может быть кодовым вектором самое большее в 2(ь-щ -М кодах, то это число и будет верхней границей для количества всех наборов длины п во всех кодах, которые приводят к ошибке декодирования. Число наборов длины п, находящихся на расстоянии г' от полученной последовательности, равно тза а. и Х с;с!:",.
Кодовыми словами в любом коде могут быть только наборы длины п, вес которых равен или больше чем йз. Полагая вес на- г) Вместо этого подмножества можно рассматривать класс всех кодов. Если проводить усреднение по всем кодам, то результат получается слабее. Первые границы случайного кодирования были границами -гого типа.
(См., ггапример, первое издание этой книги.) Приведенная здесь граница обычно называется границей случайного коднпования чс вы геркнвзинемж бора длины и в предыдущей сумме й равным !+! — 2х, получаем !+/ !+( ЕС вЂ” С( =ХС - С', ~ (л+/ — /)а, и+/ — л)/2 ч~ с(«+)-/)/2~ (л+!-!)/г л-г г л-а г где суммирование проводится по тем значениям Ь, для которых й+ ! — ! четно. Затем, суммируя по (, получаем общее число наборов длины н, находящихся на расстоянии ! от полученного набора„ которые могут быть кодовыми словами, т. е.
! !+) Х ХС с (л+!-!)вг4«+! — /))г л-! // а;/ л-гг Будем предполагать, что в том случае, когда два кодовых слова одинаково отстоят от полученного набора, происходит ошибка„ Тогда верхний предел суммирования в сумме по ) равен ). Следовательно, /+! л! ());-2(л-') ( -") ~~; ~ С(л);/-!)/«С(л+!-и/г )-г -! л-и (4.336) й- Если ! ~ дг, то, конечво„ /У(/)(общего числа кодов в классе. (4.33в) Вероятность каждой комбинации из ! ошибок равна Р!(г"-!, и число таких комбинаций составляет С„. Суммируя по ! и деля ! на общее число кодов, входящих в рассматриваемый класс, получаем верхнюю границу средней вероятности ошибок для класса хороших кодов. Поскольку число этих кодов ограничено снизу величиной 2"(" †)-', то эту величину можно использовать вместо действительного числа кодов. Далее, поскольку в классе существует по крайней мере один код, столь же хороший, как средний, то полученная граница справедлива также для наилучшего кода.
Теорема 4.10. Вероятность ошибочного декодирования для наилучшего (н, й)-кода ограничена сверху: р Т' х ) х",(л+(-!)/г,(л+!-!)/г ~'Р Я' !-(г !) !-г -! «-г г ы е л + ',) СФО" '. (4.34) г в любой из трех сумм. Это наибольшее слагаемое можно выделить путем сравнения последовательных отношений слагаемых.
Однако сначала полезно определить наибольшее слагаемое в каждой из трех отдельных сумм, Если п достаточно велико, так что множителями (2/ — д )з можно пренебречь, то первая сумма представляет собой просто часть биномиального распределения, наибольшее слагаемое в котором соответствует / — [дз/2) = Р(п — йя). Таким образом, если О ~ (и — дз)Р ( /ь — (йз/2), то наибольшим является слагаемое с номером / =Р(п — дз)+(йз/2]; при /ь — Щ21 ~(п — йз)Р наибольшим будет последнее слагаемое.
Вторая сумма обладает аналогичными свойствами. Отношение (/+ 1)-го слагаемого к /-му равно Р !п — /)~ 9!/+ !)' ' и наибольшим будет слагаемое, для которого это отношение наиболее близко к !. Снова, если и н / велики, так что единицей в знаменателе можно пренебречь, то это отношение равно 1 при /л (4,37) Таким образом, если пР, /ь + 1, то наибольшим является первое слагаемое; если /ь + 1 = пР, ( йг — 1, то наибольшим является слагаемое с номером / = пР;, если дз — 1 ( пР„ то наибольшим является последнее слагаемое. Третья сумма опять представляет собой биномиальное распределение. Следовательно, при пР ( йз наибольшим является первое слагаемое; при д ( пР ~ п наибольшим является слагаемое с номером !=пР.
Обладая этой информацией, проще определить, сравнивая последовательные отношения, какое из трех возможных слагаемых является наибольшим. Результаты этого исследования состоят в следующем: Случай /. О (йд ~ пР. Наибольшим слагаемым является слагаемое из третьей суммы с номером / = пР. Хорошей верхней границей длЯ Р, в этой области изменениЯ Ыз ЯвлЯетсЯ единица.
ПРименяя результаты приложения А к соотношению (4.32), получаем г дат ! — Р=Н! — „!. (4.38) Значение Д, соответствующее наибольшей величине отношения йл/и, для которого доминирующей является третья сумма, совпадает с шенноновской пропускной способностью канала С. Таким образом, С = 1 — Е(Р). (4.39) Случай 2. пР -йл = пР,. Наибольшим является первое слагаемое третьей суммй. Надежность для наилучшего кода в этом случае имеет следующую границу: Е) — Игп — !ой~пС~4Р447 ~х )Е( л, Р) (4.40) Здесь в правой части стоит функция, определенная в приложении А, причем это та же самая функция, которая является нижней границей сферической упаковки для Е.
Таким образом, Е = = Е(~Цп, Р) в этой области изменения а,. Из определения этой функции, данного в приложении А, следует, что необходимым и достаточным условием того, чтобы величина Е была больше нуля, является условие Щп ) Р. Но тогда и из условий (4.38) и (4.39) вытекает, что Е - С. Таким образом, для наилучшего двоичного кода длины и при й ( С вероятность ошибки стремится к нулю„когда и стремится к бесконечности.
Это частный случай основной теоремы Шеннона для каналов с шумами, в которой утверждается, что, выбирая достаточно длинные коды, можно сделать вероятность ошибки сколь угодно малой при условии, что скорость передачи не превосходит пропускной способности канала. Может быть доказано и обращение этой теоремы. Оно состоит в том, что при й ) С для канала с шумами невозможно получить стремящуюся к нулю Р,.
Случай 3. пР, (йх ( пРь, где 44РЯ (4.41) 1+ 44Р~ Величина Рь равна значению, которое принимает отношение дл/п при 1ь = пР., т. е. когда наибольшим во второй сумме является первое слагаемое. Используя результаты приложения А и равенство (4.38), получаем Е) — 1пп — 1ой Р,) Н( — ) — О(Р,)+ Е(Р„Р). (4.42) Эта нижняя граница надежности заведомо меньше, чем верхняя граница сферической упаковки. Случай 4. пРь < г1а( п. Наибольшим является то слагаемое первой суммы, для которого 1 — (йг/2) = (и — йа) Р. Поскольку в этой области изменения оа — !пп — 1ой.С„"а2 м ю=О, ) а то надежность удовлетворяет неравенству да 1 Е ) — 1он и 44РЯ (4.43) В этой области изменения скоростей граница имеет вид прямой линии: Е) 1оа( ) — 17.
(4.44) Для скоростей, заключенных между 0 н 17ь, наилучшая граница определяется соотношением (4.43) . Учитывая равенство (4.38), получаем, что в этой области (4.45) Эти результаты показывают, что граница случайного кодирования состоит из двух криволинейных участков и одного прямолинейного. Легко доказать, что в целом это непрерывная кривая "» более того, что прямая является касательной к кривым в точкад стыкоаки, так что даже производная границы непрерывна. Соотношения (4.40) — (4.42) и соотношение между й /а и скоростью передачи для кода позволяют установить нижнюю границу для кривой зависимости надежности от скорости передачи для наилучшего двоичного кода. Эта кривая изображена на фиг.
4.2 для Р = 1О-а. Она состоит из трех ненулевых участков. При С ) )7 ) 1г„ применимо соотношение (4.40). Величина 17, равна скорости передачи, соответствующей условию о,= пР„где Р., определяется равенством (4.37). Таким образом, При Й, = Й ) )гь справедливо соотношение (4А2). Величина 1гь равна скорости передачи, соответствующей условию Иа = пРь, где Р, задается равенством (4.41). Таким образом, Если бы при усреднении не были бы исключены плохие коды, то верхняя граница для Р, получилась бы несколько хуже. В частности, область, в которой справедлива оценка (4.44), простиралась бы от )г = Й, до )г = О, и соотношение (4.45) было бы неприменимо. Этот случай показан на фиг. 4.2 пунктирной линией. Интересно также отметить, что довольно хорошие коды можно получить, выбирая случайным образом некоторое не слишком большое число кодов, а затем оставляя наилучший из них.
Кодирование для таких кодов производится довольно легко, поскольку они являются линейными, и их вполне можно было бы использовать, если пренебречь трудностями, связанными с декодированием. Из соотношения (4.45) видно, что при 11 = О надежность ограничена снизу величиной '/з!ой(!( ЬГ4Р(Я, которая составляет половину величины границы сферической упаковки при Л = О. Из соотношения (4.23), записанного в асимптотической форме (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
