5.2. ПРИНЦИПЫ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

Покажем, каким образом избыточное кодирование позволяет повысить верность передачи сообщения. Как уже отмечалось, для помехоустойчивых блочных равномерных кодов Это значит, что для передачи знаков сообщения используется лишь часть возможных последовательностей, составленных из -ичных символов (часть пространства -последовательностей). Последовательности, используемые при кодировании, называются разрешенными кодовыми комбинациями, а все другие «-последовательности — запрещенными. На вход канала поступают только разрешенные комбинации. Если при передаче кодовой комбинации помехи не вызовут ошибок, то на выходе канала возникает та же разрешенная комбинация. Если же один или несколько символов принимается ошибочно, то на выходе канала может возникнуть одна из запрещенных комбинаций.

Таким образом, если комбинация на выходе канала оказывается запрещенной, то это указывает на то, что при передаче возникла ошибка. Отсюда видно, что избыточный код дает возможность обнаружить, в каких принятых кодовых комбинациях имеются ошибочные символы. Безусловно, не все ошибки могут быть обнаружены. Существует вероятность того, что, несмотря на возникшие ошибки, принятая последовательность кодовых символов окажется разрешенной комбинацией (но не той, которая передавалась). Однако при разумном выборе кода вероятность необнаруженной ошибки (т. е. ошибки, которай переводит разрешенную комбинацию в другую разрешенную комбинацию) может быть сделана очень малой.

Если принята запрещенная кодовая комбинация то, зная параметры канала, можно определить, какая из разрешенных комбинаций вероятнее всего передавалась, и произвести декодирование принятой комбинации в комбинацию, совпадающую с Если действительно передавалась то тем самым возникшие ошибки будут исправлены. Конечно, возможны случаи, когда в действительности передавалась не наиболее вероятная комбинация а какая-то другая, так что декодирование окажется неправильным. Тем не менее при достаточной избыточности кода и хорошей его структуре вероятность неисправленной ошибки может быть достаточно малой и во всяком случае значительно меньшей, чем при примитивном кодировании.

Из сказанного видно, что при избыточном кодировании возможны два основных метода декодирования — с обнаружением ошибок и с исправлением ошибок. Сущность метода декодирования с исправлением ошибок заключается в том, что все множество В принимаемых последовательностей длины разбивается на неперекрывающихся подмножеств: Если принята последовательность, принадлежащая подмножеству то считается, что передавалась кодовая комбинация Естественно, что в подмножество Вгследует включить те запрещенные комбинации при приеме которых наиболее вероятной переданной комбинацией является

При декодировании с обнаружением ошибок множество В разбивается на подмножеств, из которых содержат каждое по одной (разрешенной) кодовой комбинации, а подмножество все остальные (запрещенные) комбинации. В некоторых системах связи принятая запрещенная комбинация просто отбрасывается и не поступает к получателю. Это обоснованно в тех случаях, когда потеря переданного сообщения значительно менее опасна, чем получение ложного сообщения. Чаще при декодировании с обнаружением ошибки ошибочно принятая кодовая комбинация не теряется, а восстанавливается специальными методами. Среди них наибольшее распространение получил метод переспроса (см. § 5.6).

Необходимо отметить, что правило декодирования с обнаружением ошибок однозначно определяется кодом (т. е. выбором разрешенных комбинаций) и не зависит от свойств канала. При исправлении ошибок, наоборот, возможны различные правила декодирования, поскольку каждую из запрещенных комбинаций можно включить в любое из подмножеств В зависимости от свойств канала то или иное правило является предпочтительным.

Существуют и смешанные методы декодирования, когда некоторые ошибки исправляются, а некоторые только обнаруживаются

Здесь множество В также разбито на подмножеств, но в подмножество помимо разрешенных комбинаций входят и некоторые близкие к ним запрещенные (исправляемые), а в только те запрещенные комбинации, которые не могут быть достаточно надежно исправлены.

Говорят, что в канале произошла ошибка кратности А, если в кодовой комбинации символов приняты ошибочно. Легко видеть, что кратность ошибки есть не что иное, как расстояние Хэмминга между переданной и принятой кодовыми комбинациями, или, иначе, вес вектора ошибки (см. с. 65).

Рассматривая все разрешенные кодовые комбинации и определяя кодовые расстояния между каждой парой, можно найти наименьшее из них где минимум берется по всем парам разрешенных комбинаций. Это минимальное кодовое расстояние является важным параметром кода. Очевидно, что для простого кода

Обнаруживающая способность кода характеризуется следующей теоремой.

Если код имеет и используется декодирование по методу обнаружения ошибок, то все ошибки кратностью обнаруживаются. Что же касается ошибок кратностью то одни из них обнаруживаются, а другие нет.

Для доказательства достаточно вспомнить, что кодовое расстояние между посланной и принятой комбинациями равно Следовательно, если принятая комбинация не может быть разрешенной, так как это противоречило бы определению Поэтому она будет принадлежать подмножеству запрещенных комбинаций, т. е. ошибка будет обнаружена. При принятая комбинация может оказаться разрешенной и ошибка останется необнаруженной, но часто и в этом случае принятая комбинация оказывается запрещенной и ошибка обнаруживается.

Процесс исправления ошибок рассмотрим сначала для симметричного канала без памяти. В таком канале, описанном в § 3.4, по определению, вероятность правильного приема символа не зависит от того, какой символ передается, а также от того, как приняты остальные символы. Вероятность того, что вместо переданного символа будет принят символ равна Отсюда легко вывести, что вероятность получения на выходе канала комбинации если на вход подана комбинация равна

Это следует непосредственно из теоремы умножения вероятностей независимых событий и из того, что для перехода в необходимо, чтобы на определенных разрядах произошли определенные ошибки, а на остальных разрядах символы были приняты верно.

Таким образом, в симметричном канале без памяти зависит только от кодового расстояния между В случаях, когда что практически всегда выполняется, выражение (5.5) монотонно убывает с увеличением Следовательно, вероятность принять комбинацию тем больше, чем меньше ее кодовое расстояние от переданной комбинации

Аналогично тому, как в демодуляторе по приходящему искаженному сигналу определяется передававшийся кодовый символ, в декодере по искаженной последовательности символов необходимо определить действительно передававшуюся кодовую комбинацию. Разумеется, решение, принимаемое декодером, не всегда является верным. Однако можно добиваться минимума вероятности ошибочного декодирования. Если считать, что все разрешенные кодовые комбинации передаются равновероятно, то, как было показано в § 4.2, минимальную вероятность ошибки обеспечивает решение по максимуму правдоподобия. Другими словами, при декодировании запрещенной комбинации декодер должен выдавать ту разрешенную комбинацию для которой вероятность перехода больше, чем при Это правило декодирования по максимуму правдоподобия можно записать сокращенно так:

В симметричном канале без памяти это значит, что запрещенную комбинацию следует декодировать, как ту разрешенную комбинацию которая находится на наименьшем расстоянии от Иначе говоря, в подмножество следует включить все те комбинации которые ближе (в смысле Хэмминга) к чем к любой другой разрешенной комбинации.

Такое декодирование по наименьшему расстоянию является оптимальным для симметричного канала без памяти. Однако для других каналов это правило может и не быть оптимальным, не соответствовать максимуму правдоподобия.

Исправляющая способность кода при этом правиле декодирования определяется следующей теоремой.

Если код имеет и используется декодирование с исправлением ошибок по наименьшему расстоянию, то все ошибки кратностью исправляются. Что же касается ошибок большей кратности, то одни из них исправляются, а другие нет.

Для доказательства покажем, что в условиях теоремы (при действительно переданная комбинация ближе (в смысле Хэмминга) к принятой комбинации нежели любая

другая разрешенная комбинация. Предположим противное, т. е. что существует разрешенная комбинация для которой Наосновании (2.92) отсюда следует, что Но условию теоремы Отсюда что противоречит определению Это противоречие и свидетельствует о справедливости теоремы.

Две доказанные теоремы позволяют оценить вероятность ошибочного декодирования (при декодировании с исправлением ошибок) и вероятность необнаруженной ошибки (при декодировании с обнаружением ошибок) в симметричном канале без памяти. Для этого напомним, что вероятность возникновения каких-либо ошибок кратностн определяется известным биномиальным законом

Эта формула следует из того, что ошибки в таком канале являются независимыми событиями с вероятностью

Используя доказанные теоремы и равенство (5.7), получаем следующие оценки для вероятности ошибочного декодирования при коррекции ошибок и для вероятности необнаруженной ошибки при обнаружении ошибок:

Здесь обозначает наибольшую целую часть [знак неравенства в (5.8) и (5.9) ставится потому, что код, вообще говоря, может исправлять некоторые ошибки кратности и выше и обнаруживать ошибки кратности и выше].

Помехоустойчивые коды можно применять и в дискретных каналах со стиранием (см. с. 102). Если в принятом блоке ошибок нет, но имеется стертых (не опознанных модемом) символов, то при эти стирания могут быть исправлены при декодировании по минимуму расстояния. Это вытекает из определения так как для того, чтобы две комбинации оказались неразличимыми, необходимо стереть не менее символов. Можно показать также, что при декодировании по минимуму расстояния в канале с ошибками и стираниями гарантированно исправляются ошибок и стираний, если

Неравенства (5.8) и (5.9) иллюстрируют важную роль как основного показателя исправляющих и обнаруживающих свойств кода в симметричном канале без памяти (чем больше тем меньше Поэтому задача кодирования состоит в выборе кода, обладающего максимально достижимым Впрочем, такая формулировка задачи неполна. Увеличивая длину кода и сохраняя число кодовых комбинаций можно получить сколь угодно большое значение Проще всего это достигается повторением символов кодовых комбинаций. Но совершенно очевидно, что такое «решение» задачи не представляет интереса, так как с увеличением уменьшается возможная скорость передачи информации от источника. Если длина кода задана, то

можно получить любое значение превышающее уменьшая число комбинаций Поэтому задачу поиска наилучшего кода (в смысле максимального следует формулировать так: при заданных найти код длины содержащий комбинаций и имеющий наибольшее возможное кмша. В общем виде эта задача в теории кодирования не решена, хотя для многих значений и ее решения получены.

Эффективность помехоустойчивого кода возрастает при увеличении его длины. Это вытекает из формулы (3.79), так как вероятность ошибочного декодирования уменьшается при увеличении длины кодируемого сообщения.

Будем рассматривать не один определенный код, а множество различных помехоустойчивых кодов, имеющих одинаковую относительную скорость [см.

Расположим коды в порядке увеличения (а следовательно, и . Предположим, что эти коды используются в симметричном канале без памяти, вероятность ошибки в котором равна Математическое ожидание кратности ошибок в кодовой комбинации

По закону больших чисел при сколь угодно малом положительном вероятность того, что стремится к 1, когда неограниченно возрастает. Следовательно, если из нашего множества кодов выбрать код с достаточно большим то с вероятностью 1—б (где сколь угодно малое положительное число) кратность ошибок будет лежать в пределах

Если для выбранного кода то он позволяет исправлять все ошибки кратностью, меньшей а значит, в соответствии с (5.10), с вероятностью 1—б все кодовые комбинации будут декодированы верно. Таким образом, для того, чтобы с увеличением вероятность правильного декодирования в симметричном канале без памяти стремилась к единице, достаточно выполнить условие

В связи с этим возникает вопрос, при каких значениях и условие (5.11) выполняется.

При рассмотрении данного вопроса ограничимся для простоты двоичным случаем В теории кодирования доказывается, что

при достаточно больших длинах блоков всегда существуют коды с ймин, удовлетворяющим неравенству

где значение функции вычисленное при Неравенство (5.12) играет важную роль в теории кодирования и называется границей Варшамова — Гильберта.

Очевидно, что левая часть (5.12) есть скорость двоичного кода. Поэтому из неравенств (5.11) и (5.12) следует, что всегда можно построить код, для которого вероятность правильного декодирования в двоичном симметричном канале стремится к единице, когда скорость кода удовлетворяет неравенству

С другой стороны, из теоремы Шеннона (см. § 3.7) следует, что существует код, позволяющий обеспечить сколь угодно малую вероятность ошибочного декодирования, если относительная скорость передачи информации меньше пропускной способности Ссимв. В двоичном симметричном канале, согласно Следовательно, оценка скорости передачи неравенством (5.13) слабее, чем даваемая теоремой Шеннона. Это объясняется тем, что неравенство (5.11) является достаточным, но не необходимым условием, а (5.12) дает лишь нижнюю границу для Тем не менее, проведенные рассуждения об асимптотике ймин имеют важное значение, особенно при рассмотрении проблемы сложности декодирования.

Полученные выше результаты на первый взгляд говорят о том, что помехоустойчивое кодирование (по крайней мере, для симметричного канала без памяти) реализуется весьма просто. В память кодирующего устройства (кодера) записываются разрешенные кодовые комбинации выбранного кода и правило, по которому с каждым из сообщений источника сопоставляется одна из таких комбинаций. Данное правило известно и на декодере.

Получив от источника определенное сообщение, кодер отыскивает соответствующую ему комбинацию и посылает в канал. В свою очередь, декодер, приняв комбинацию, искаженную помехами, сравнивает ее со всеми комбинациями списка и отыскивает ту из них, которая ближе остальных к принятой. Однако даже при умеренных значениях такой способ оказывается весьма сложным. Покажем это на примере.

Пусть для двоичного кода выбрано значение обеспечивающее приемлемую вероятность выполнения (5.10), а скорость кода примем равной 0,5. При этом условие (5.13) выполняется для любого двоичного симметричного канала, у которого Тогда Таким образом, кодовая таблица должна содержать 1015 кодовых комбинаций, или

кодовых символов. В аппаратуре кодера и декодера эти таблицы «записываются» на двоичных запоминающих ячейках: например, магнитных сердечниках, магнитной ленте, триггерах, криотронах и т. п. Предположим, что в результате успехов микроэлектроники, через несколько лет удастся производить подобную запись, затрачивая на каждый двоичный символ объем в или Такие запоминающие устройства в настоящее время можно найти только на страницах фантастических романов. Вся таблица в данном случае займет объем Это объем куба, каждая сторона которого равна Очевидно, что изготовление такого устройства совершенно нереально. Но им не исчерпываются кодер и декодер. В частности, в декодере необходимо проделать операций, сравнивая символы принятой комбинации с символами, хранящимися в таблице. Так как на это можно отвести только время порядка длительности кодовой комбинации (например, 1 с), а число операций, выполняемых в одну секунду электронными логическими схемами, не превышает в настоящее время то пришлось бы применить около 1010 параллельно работающих схем сравнения.

Таким образом, применение достаточно эффективных (а значит, и достаточно длинных) кодов при табличном методе кодирования и декодирования технически невозможно. Поэтому основное направление теории помехоустойчивого кодирования заключается в поисках таких классов кодов, для которых кодирование и декодирование осуществляются не путем перебора таблицы, а с помощью некоторых регулярных правил, определенных алгебраической структурой кодовых комбинаций. Один из такий классов представляют линейные коды, которые, в свою очередь, содержат различные подклассы кодов, отличающиеся теми или иными свойствами. Некоторые из них позволяют существенно упростить построение кодера и декодера, даже при значениях Оказывается выгодным применять коды с меньше оптимального, если их структура позволяет упростить кодирование и особенно декодирование.