Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 17
Текст из файла (страница 17)
Согласно теореме Шеннона, сообщения источника с управляемой скоростью можно закодировать так, чтобы передавать их сколь угодно точно по дискретному каналу со скоростью 1'(х, х'), меньшей пропускной способности С. Сообщения источника с фиксированной скоростью можно передавать сколь угодно точно, если производительность источника Н'(х) меньше пропускной способности канала С. Заметим, что пропускная способность дискретного канала С не может быть больше пропускной способности С„заключенного в нем непрерывного канала. Это следует из того, что скорость передачи информации не может возрасти при преобразовании принятого непрерывного сигнала г'(1) в кодовый символ у'.
Обычно С<С» так как преобразование х'(!) в у' является необратибл 83 мым. Если не считать модулятор и демодулятор заданными, то можно в принципе произвести кодирование сообщения для непрерывного канала и передавать его сколь угодно точно со скоростью, око,чь угодно близкой к С„, т. е. большей, чем С, Полагая модулятор и демодулятор заданнымн и производя кодирование в дискрет. ном канале, мы теряем эту возможность и вынуждены передавать сообщение со скоростью, меньшей С.
Тем не менее на эту жертву охотно идут, поскольку операции кодирования и декодирования в дискретном канале летуче поддаются математическому анализу и обычно проще осуществляются технически, чем в непрерывном канале. Здесь слова «легче» и «проще» не следует понимать в абсолютном смысле. Теория кодирования в дискретном канале основывается на достаточно сложном математическом аппарате, а практнческое осуществление кодеров и декодеров часто наталкивается на технически непреодолимые трудности.
Из задачи кодирования в дискретном канале развилась теория помехоустойчивых кодов. Не имея возможности изложить эту теорию подробно, ограничимся лишь ее основными положениями и некоторыми результатами, которью будут даны без доказательств, поскольку в настоящее время существует достаточно обширная монографическая литература, относящаяся к двум основным направлениям — вероятностной [9, 10) и алгебраической [11, 12) теории кодирования.
Сущность помехоустойчивого кода покажем на примере блочных кодов, отличающихся тем, что с каждым элементарным сообщением илн с каждой последовательностью из определенного числа элементарных сообщений сопоставляется блок из а символов [кодовая комбцнаг!ил). Пусть выбрано некоторое значение л. Можно построить Ф=т" различных последовательностей символов кода с основанием иь Выберем из У возможных кодовых комбинаций некоторое число Ж„<Й комбинаций, которые будем называть разрешенными„и сопоставим их с определенными последовательностями сообщений источника.
Остальные У вЂ” Ж«комбинаций являются запрещенными и не используются для передачи сообщений. При передаче по каналу с шумамн некоторые кодо. вые символы будут приниматься ошибочно, в результате 84 чего принятая кодовая комбинация будет отличаться от переданной.
Если принятая с ошибками кодовая комбинация окажется одной из разрешенных, то ошибки пе будут обнаружены и полученное в результате декодирования сообщение будет отличаться от переданного. Однако, если й««Л', разрешенные комбинации могут быть выбраны с учетом свойств канала так, чтобы вероятность получения ошибочной разрешенной комбинации была очень мала. Как правило, в результате ошибочного приема отдельных символов принятая кодовая комбинация окажется запрещенной, что н указывает на наличие ошибок. Возможны два основных метода декодирования при использовании помехоустойчивых кодов, декодирование с обнаружением ошибок и декодирование с исправлением ошибок.
При первом методе принятая запрещенная кодовая комбинация не преобразуется в сообщение и заключенная в ней информация либо полностью теряется, либо восстанавливается путем повторной передачи или какими-либо иными методами. В ряде систем связи по условиям нх применения очень важно не выдавать получателю ложных сообщений, тогда как потеря отдельных сообщений не так страшна, Г!риме~яя декодирование с обнаружением ошибок, можно сравнительно простыми средствами уменьшить вероятность приема ложного сообщения до любой заданной величины и добиться практически полной верности декоднрованных сообгцений ценой отбраковки значительного числа кодовых комбинаций с обнаруженными ошибками.
Декодирование с обпарун'синем ошибок нашло широкое применение в системах связи с переспросом, в которых наличие обратной связи позволяет восстановить информацию, содержавшуюся в принятых запрещенных комбинациях. Эти системы будут подробно рассмотрены в гл. 11. При декодировании с исправлением ошибок принятые запрещенные кодовые комбинации преобразуются декодером [второй решающей схемой) в сообщение по некоторым правилам, установленным для данной системы связи.
Эти правила определяются в соответствии с выбранным статистическим критерием. В частности, если в основу правил декодирования положен критерий идеального наблюдателя, то опн обеспечивают наименьшую возможную в данных условиях вероятность оши- 85 бочного декодирования. Чаще правила декодирования основываются на критерии максимального правдоподобия, который совпадает с критерием идеального наблюдателя, если все разрешенные кодовые комбинации поступают на вход канала с одинаковыми вероятностями н независимо друг от друга. Если это условие не выполнено, то вероятность ошибочного декодирования при критерии максимального правдоподобия будет несколько большей, чем прп критерии идеального наблюдателя. Все же она может быть в принципе получена сколь угодно малой при достаточно большой длине блока и, если количество разрешенных кодовых комбинаций гго удовлетворяет условию о!од г"сго<ггС. (2.22) Заметим, что разрешенные кодовые комбинации становятся равновероятпыми и независимыми, если до применения корректирующего кода устранена избыточность сообщения методамн, описанными в 5 2.3.
В этом случае энтропия, приходящаяся на кодовую комбинацию, равна 1одгУо и поскольку в единицу времени передается о/и кодовых комбинаций, то количество информации, поступающее на вход канала в единицу времени, равно — 1оп йсо и неравенство (2.22) означает, что скорость передачи информации должна быть меньше пропускной способности канала.
Возмонсны также и смешанные методы декодировання, когда в одних случаях производится исправление ошибок, а в других — только их обнаружение. Применение корректирующего кода означает введение избыточности в последовательность кодовых символов, используемой для повышения верности приема. Величину избыточности можно вычислить, если учесть, что максимальная энтропия кодовой комбинации, содержащей и символов при основании кода иг (т.
е. энтропия, которая имела бы место, если бы все т" кодовых комбинаций были разрешены и передавалнсь с равными вероятностями и независимо), равна гг !оп ггг. Эта избыточность в соответствии с (1.12) равна (2.23) г,=1— о 1оя т 86 Величину 1 — г, =- ' называют эффективностью 1оя го, п1оя т кода. Необходимая избыточность корректирующего кода может быть найдена из условия (2.22) с учетом (2.23): г„)! — —,, С -О (2.24) где Со=- о 1оц ги — пропускная способность канала без шумов. Таким образом, она определяется отношением С/Со. Что же касается вероятности ошибочного декодирования, то она зависит не только от г„, но и от длины кодовой комбинации гг и от выбора разрешенных кодовых комбинаций. При выполнении условия (2.24) для уменьшения вероятности ошибочного декодирования нужно увеличивать и. Очень важным является то обстоятельство, что сложность кодера и декодера обычно очень быстро возрастает с увеличением и.
В особенности это относвтся к декодеру. Рассмотрим, например, следующий универсальный (пригодный для любого кода) метод кодирования и декодирования. 1Тередаваемое сообщение анализируется в кодере и заменяется в соответствии с используемым кодом одной из разрешенных кодовых комбннаций. гТля этого в памяти кодера должны храниться все /гго разрешенных комбинаций, содержащих йои!оя'иг двоичных единиц.
(! — о ) п Учитывая, *гго из (2.23) следует Ж,= ги ", объем П вЂ” „1 памяти кодера должен равняться т " и1оцггг двоичных единиц. Принятая кодовая комбинация сравнивается с комбинациями, хранящимися в памяти декодера, каждой из которых соответствует определенное решение. Очевидно, что при таком методе декодирования декодер должен хранить все возможные кодовые комбинации, как разрешенные, так и запрещенные, т. е. иметь объем памяти, равный и"гг!ориг двоичных единиц. Таким образом, объемы памяти кодера и декодера с увеличением и растут более быстро, чем по закону экспоненты.
В результате ухсе при значении и, равном 30, необходимый объем памяти декодера для такого универсального метода (полагая т=2) достигает величины порядка 87 10'е дв. ед., т. е. во много раз больше технически достижимого. С другой стороны, для получения высокой верности приема с помощью корректирующих кодов часто оказывается необходимым применять значения и порядка сотен и даже больше. Поэтому основной задачей современной теории кодирования является отыскание таких кодов, которые позволяют осуществлять обнаружение и исправление ошибок пе путем сравнения с хранящимися в памяти кодовыми комбинациями, а с помощью относительно простых операций, производимых над принятой кодовой комбинацией. В этом направлении уже имеются некоторые достижения.
Предложены коды, при применении которых сложность кодера и декодера увеличивается с ростом л не экспоненциально, а пропорционально некоторой небольшой степени и [10, 11, 13). Краткие сведения об этих кодах будут приведены в последующих параграфах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
