Помехоустойчивое кодирование

1.Теоретическая часть

2.Задание Заключение Список литературы кодирование помехоустойчивое сообщение

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

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

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

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

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

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

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

Рассматривая все разрешенные кодовые комбинации и определяя кодовые расстояния между каждой парой, можно найти наименьшее из них d=min d (i;j), где минимум берется по всем парам разрешенных комбинаций. Это минимальное кодовое расстояние является важным параметром кода. Очевидно, что для простого кода d=l.

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

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

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

Процесс исправления ошибок рассмотрим сначала для симметричного канала без памяти. В таком канале по определению, вероятность правильного приема символа 1-р не зависит от того, какой символ передается, а также от того, как приняты остальные символы. Вероятность того, что вместо переданного символа bi будет принят символ bj (i=j) равна р/(т—1). Отсюда легко вывести, что вероятность получения на выходе канала комбинации bj, если на вход подана комбинация bi

P (bj|bi)=[p/(m-1)]d (i;j)(1-p)n-d (i;j)

Это следует непосредственно из теоремы умножения вероятностей независимых событий и из того, что для перехода bi в bj необходимо, чтобы на определенных d{i; /) разрядах произошли определенные ошибки, а на остальных разрядах символы были приняты верно.

Таким образом, в симметричном канале без памяти ,

P (bj;bi)

зависит только от кодового расстояния между bi и bj. В случаях, когда p<(m—l)/m, что практически всегда выполняется, выражение монотонно убывает с увеличением d (i; j). Следовательно, вероятность принять комбинацию bj тем больше, чем меньше ее кодовое расстояние от переданной комбинации bj.

Задачей декодера является принятие решения о том, какая кодовая комбинация передавалась, если принята комбинация bj, разумеется, решение, принимаемое декодером, не всегда верное. Однако можно добиваться минимума вероятности ошибочного декодирования. Пусть P (bi|bj) — условная вероятность того, что передавалась комбинация bi, если принята комбинация bj. Эту условную вероятность называют апостериорной вероятностью в отличие от безусловной априорной вероятности Р (bi) того, что передается bi, когда ничего еще не известно о принятой комбинации. Предположим, что декодер по принятой комбинации bj решил, что передавалась комбинация bft. Вероятность того, что это решение верно, очевидно, равна P (bi|bj). Чтобы эта вероятность была максимально возможной, декодер должен из всех разрешенных комбинаций bi (i=l, …, М) выбрать ту, для которой апостериорная вероятность максимальна. Это правило декодирования. по максимуму апостериорной вероятности можно записать сокращенно так:

max P (bi|bj).

Из теории вероятности известно, что P (bi|bj)= P (bi)(P (bj|bi)/P (bj)) (5.11) Формула Байеса.

Если, как часто бывает на практике, все разрешенные кодовые комбинации равновероятны (P (bi) =const=l/M), то из (5.11) следует, что максимум апостериорной вероятности совпадает с максимум условной вероятности P (bj|bi), которую называют функцией правдоподобия1. Правило декодирования по максимуму правдоподобия можно сокращенно записать так:

max P (bj|bi)

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

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

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

Если код имеет d>2 и используется декодирование с исправлением ошибок по наименьшему расстоянию, то все ошибки кратностью q

Для доказательства покажем, что в условиях теоремы (при q<.d (i; j) отсюда следует, что d{k; i)<=d (k; j) + d (i; j)<2d (i; j). Но по условию теоремы d (k; j)=q<.d/2. Отсюда d (k; i)

Полученные результаты можно выразить следующими формулами:

qo

где qО — кратность гарантированно обнаруживаемых ошибок в режиме, когда ошибки только обнаруживаются; qи — кратность гарантированно исправляемых ошибок.

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

p (q) = Сnqpq (1 — p) n-q. (5.14)

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

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

Pо.д? Сnqpq (1 — p) n-q (5.15)

Рн.о? Сnqpq (1 — p) n-q (5.16)

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

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

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

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

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

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

Пусть для двоичного кода выбрало значение n = 100, а скорость кода (logM)/n примем равной 0,5. Тогда logM = 50 и М = 2 501 015. Таким образом, кодовая таблица должна содержать 1015 кодовых комбинаций, или 100 * 1015=1017 кодовых символов. В аппаратуре кодера и декодера эти таблицы «записываются» на двоичных запоминающих ячейках: например, магнитных дисках, магнитной ленте, триггерах, криотронах и т. п. Предположим, что в результате успехов микроэлектроники через несколько лет удастся производить подобную запись, затрачивая на каждый двоичный символ объем в 10−5 мм3 или 10−8 см3. Такие запоминающие устройства в настоящее время можно найти только на страницах фантастических романов. Вся таблица в данном случае займет объем 1017- 10−8=l09 см3. Это объем куба, каждая сторона которого равна 10 м. Очевидно, что изготовление такого* устройства совершенно нереально. Но им не исчерпываются кодер и декодер. В частности, в декодере необходимо проделать 1017 операций, сравнивая символы принятой комбинации с символами, хранящимися в таблице. Так как на это можно отвести только время порядка длительности кодовой комбинации (например, 1 с), а число операций, выполняемых в одну секунду электронными логическими схемами не так велико.

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

Задание Необходимо закодировать и передать 7 различных сообщений по двоичному симметричному каналу без памяти. Вероятность ошибки при передаче символа по каналу р=0.2. Кодирование производится избыточным кодом qи=1…4

Рассчитать в зависимости от изменения qи:

d; n; r; qо кода.

Вероятности ошибочного декодирования и необнаруженной ошибки.

Время передачи по каналу одного сообщения, если vк=1000 сим/с.

Построить графики указанных зависимостей.

Сначала рассчитаем параметры кода:

А) по известной кратности исправляемых ошибок найдем минимальное кодовое расстояние d. Известно, что для нечетных d, для четных d. Отсюда находим:

канала

Б) найдем количество избыточных символов кода

В)определим количество информационных символов k как наибольшее ближайшее целое к log7, то k=3.

Г) найдем общую длину кодовой комбинации n=k+r:

Д) обнаруживающая способность кода

Затем определяем вероятность ошибочного декодирования И вероятность необнаруженной ошибки

Здесь обозначает наибольшую целую часть вероятность ошибочной передачи одного кодового символа; - количество сочетаний из n элементов по q:

Рис. 1 зависимость

Рис. 2 зависимость

Рис. 3 зависимость

Рис. 4 зависимость

Заключение

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

Список использованной литературы Зюко А. Г. «Теория передачи сигналов». — М.: Радио и связь, 1986 г.

2. Козлов С. В., Седов С. С. «Теория электрической связи». Пособие по курсовой работе. Казань. 2001 г.