Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 19
Текст из файла (страница 19)
В связи с этим возникает вопрос, каково наибольшее возможное значение им„н прн заданных № и и либо каково наибольшее значение № прн заданных и и дм . Точного выражения, которое давало бы ответ на этот вопрос, не существует, однако известны некоторые оценки, Приведем без доказательств две наиболее важные оценки, относящиеся к двоичным корректирующим ко- 93 с„ »св а ее дисперсия иг (г1) г 0 25п )у о и»н= (2.34) с„" »=О дам (т=2).
Как показал Хемминг 1!5), для любого двоичного кода. (2.33) Те коды, для которых в (2.23) имеет место равенство, называются плотно упакованными. Помимо примитивных кодов известны и некоторые плотно упакованные корректирующие коды, например код, состоящий из двух комбинаций; 000 и 111, для которого №=2, п=З и (»,=З. С другой стороны Р. Р. Варшамов показал (11], что при любых и и г(,„„существуют коды, для которых Задача конструктивного построения оптимального (для постоянного симметричного канала) кода, имеющего при заданных и и № наибольшее значение Йяя„ в общем виде не решена.
Одним из способов приближения к решенного этой задачи (при достаточно большом и), как это ни парадоксально, является случайный выбор разрешенных кодовых комбинаций из всех пг" возмо>кных блоков символов длиной п. Поясним это на примере двоичных кодов (>и = 2) . 11усть случайным образом выбрано № последовательностей символов «О» и «1» длиной и. Это можно сделать, например, подбрасывая п№ раз монету и записывая «1», когда выпадает герб, и «О» в противном случае. Рассмотрим любую пару из построенных таким образом комбинаций.
Расстояние И между этими комбинациями является случайной величиной. Определим ее математическое ожидание и дисперсию. Очевидно, вероятность того, чта в некотором разряде рассматриваемые комбинации будут иметь различные символы, равна 0,5. Поскольку события, заключающиеся в несовпадении символов в разных разрядах данных двух кодовых комбинаций, независимы, то задача сводится к схеме Вернули (последавательностя нз п неза- 94 внсимых испытаний) с вероятностью положительного исхода, равной 0,5.
Прн этом, как известно, математическое ожидание расстояния И равно гТ= 0,5п, При п))1, воспользовавшись интегральной предель- ной теорег>ой Муавра — Лапласа (см. например (16)), можно оценить вероятность того, что хеммингово рас- стоиние между двумя случайно выбранными кодовыми комбинациями окажется меныпе, чем (0,5 — 6)и, где 6— некоторое малое положительное число; Р(д«".(0,5 — 6)п~ «, -гг>'й — е г(з = Г( — 26 )Гй). (2.35) Р 2л,1 При увеличении п функция Лапласа г ( †26 )/и) быстро стремится к нулю. Поэтому при любых положительных 6 и у можно найти такое и, что с вероятностью, большей 1 — у, хеммингово расстояние между любой парой случайно выбранных кодовых комбинаций будет больше, чем (0,5 — 6)п. Приведенные рассуждения дают только качественное подтверждение того, что при случайном выборе кода можно с вероятностью, близкой к единице, получить болыпое хеммингово расстояние между разрешенными кодовыми комбинациями.
Для того чтобы определить скорость передачи информации при случайном кодировании, оценим вероятность ошибочного декодирования при п))1. Предположим, что случайным образом выбраны № разрешенных кодовых комбинаций, которые известны как на передаюгцей, так и на приемной стороне. Пусть одна из нпх (комбинация А) послана по каналу связи. Принятая комбинапия А; вообще говоря, будет содержать ошибочные символы.
Математическое ожидание количества ошибочных символов г в А' равно ир, где р — вероятность ошибки в канале. Если а и Д вЂ” произвольно выбранные сколь угодно малые положительные 95 (2.36) Поскольку величина л очень велика, можно, воспользовавшись приближенной формулой Сгирлинга, заменить правую часть (2.36) следующим образом: Но с вероятностью 1 — а отношение — меньше чем Р+р. л Обозначим Р+р==. р". Тогда с вероятностью ! — н на ~~/ Р л —.'" (! Ра) и Р и'. (2.38) Любая из этих й комбинаций может быть разрешенной с вероятностью 1аа(2п, а вероятность того, что ни одна из и комбинаций (кроме заведомо известной комбинации Л) не принадлежит к числу разрешенных, равна ( 2н ) ' 2н (2.39) ! * Веранеистно (2.36) справедливо прн г к. — л, поскоаьку 2 ! ! С„нсарастает с унеличением ! от ! до л/2, Так как Рк,.
всегда можно выбрать ! тан, чтобы ато условие ныполиилось. 96 то величины, то на основании закона больших чисел су* ществует такое значение ль что при л>и! с вероятностью 1 — а величина г не превзойдет л(Р+[!). Ошибочное декодирование произойдет в том случае, если существует хотя бы одна разрешенная комбинация В (помимо Л), расстояние которой до принятой комбинации Л' меньше чем г. Оценим вероятность этого. Обшее число й комбинаций, находящихся на расстоянии «е большем г от комбинации Л', равно * Таким образом, вероятность Я(л) правильного декоди- рования принятой комбинации Л' оценивается следую- щим выражением: „~/ Р*л и — р а а! и — (! — р,а а 'г 2а,(! Ра) ! Р ) =1 — и — !У а/ ' " 2 л!'+" "и" +!' 2и (! — Ра) (2.40) где логарифм берется по основанию 2.
Введем еше одно обозначение: С =в[1+Р ~алвР +(1 — Р )1о2(1 — Р )]. (241) Легко убедиться, что С' меньше пропускной снос б канала: й спосо ности С = О [1+Р !ОД'Р+(! — Р) 1ОД'(1 — Р)], (2.42) и стремится к ней, когда р стремится к нулю. Переписан (2.40) следующим образом: и Я (л)» 1 — а — 1гг Р'л й( 2 Н 2е(! а) а видим, что с увеличением л вероятность правильною декодировании стремится к 1 — а при условии, что величина й!о удовлетворяет неравенству л — с* Р7акл ! 2 (2.43) (2.44) где Т> ! 2 ' В частности, вто будет верно, если 7у„= ! 2" Учит ывая» что п рн достаточпО большом л велианща аа может быть сколь угодно малой, а величина С' — сколь угодно близкой к С, можно утверждать, что при случайно выбранном коде вероятность правильного декодйрования принятой комбинации сколь угодно близка 7 — 2447 к единице (для достаточно большого и), если число разрешенных комбинаций ~1 с (2.45) О лим наконец, скорость передачи информации и и таком кодировании.
Так как вероятность пр при таком ного декодирования сколь угодно близка к ед б. е инице, то количество переданной по каналу ипф р р нфо мации равно энтропии кодовой комбинации. Если р р Е . все азрешенные комбинации выбираются независимо и равновероятно, то энтропия ия на кодовую комбинацию равна д а энтропия на каждый переданный символ Н (у) = — 108 У . 1 (2.46) Следовательно, скорость передачи информации Р(у, у)= В(у)= 1а)У, или, подставляя сюда (2А5), 1'(у, у')=С вЂ” о ~ (2.47) С всличением и второй член стремится к пулю, т. е. скорость передачи информации может б у ув быть сколь угод- но близкой к пропускной способности канала. Разумеется, при описанном случайном в р ыбо е кода существует некоторая вероятность выбрать «плахой» кад.
апример, . Н может случиться (хатя и с очень малой 1аниАиВбу- вероятностью), что какие-то две комбинации и дут совпадать друг с .другом либо иб отличаться только в одном р разряде. При передаче комбинации она на как В, с большой вероятностью будет декодирова б . Е и эта имеет место для нескольких пар ности комбинаций, то такой код не обеспечит высокой верн декодирования.
нк кото ой Вероятность правильного приема, оценку которо (2.45) является по существу совместной вероят- дает (. а, я » ко а и правух событий — выбора «хорошего» . д ее под об- вильного декодирования при этом коде. Более р 93 ный анализ (9) приводит к следующему результату. Среди случайно выбранных кодов существуют «хорошие» коды, для которых вероятность ошибочного декодирования Р(и) =1 — Щи) при достаточно большом и подчиняется неравенству Р(и)«,Ае ~'ю", (2.48) где А — некоторый коэффициент, медленно меняющийся с ростом и; Е (В) — функция скорости передачи информации Й = = — 1одЛ;, положительная при )с С и равная и нулю при Я=С. Чта касается вероитности Р„выбрать «плохай» код, для которого (2.48) ле имеет места, то она также стремится к нулю с ростом и, причем значительно быстрее.
чем вероятность ошибочного декодирования. Таким образом, если значение и выбрано так, чтобы обеспечить достаточно малую вероятность ошибочного декодирования (2.48), то практически с вероятностно 1 случайно выбранный и-разрядный код будет хорошим. Казалось бы, что получевные результаты полностью решают задачу безошибочной передачи информации со скоростью, близкой к пропускной способности постоянного симметричного двоичного канала.
Однако практическое использование чисто случайно~о кода сталкивается с непреодолимыми в,настоящее время, а также, по-видимому, и в ближайшие десятилетия, трудностями. Дело в том, что единственным методом кодирования и декодирования (при случайном коде) является хранение в памяти кодера и декодера по крайней мере всех разрешенных комбинаций и сравнение их с принятой комбинацией. При значениях и, обеспечивающих достаточно малую вероятность ошибочного декодирования, необходимый объем памяти существенно превышает все достигнутое соврсменной техникой. Именно вследстние этога чисто случайное кодирование не нашло практического применения и усилия исследователей были направлены на поиски регулярных (яли полурегулярных) методов кодирования, при которых можно сформулировать определенные правила пре99 образовании соообщений в кодовые комбинации, а также правила декодирования с обнаружением и исправлением ошибок и построить по этим правилам относительно просто реализуемые логические схемы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
