Мера избыточности кода Введем ряд обозначений- М0 ~ полное множество всех возможных комбинаций кода с м
Работа добавлена на сайт samzan.net:
PAGE 70
3. ОБЩИЕ ПРИНЦИПЫ ОБНАРУЖЕНИЯ И ИСПРАВЛЕНИЯ ОШИБОК ИЗБЫТОЧНЫМИ КОДАМИ
3.1. Мера избыточности кода
Введем ряд обозначений: М0 – полное множество всех возможных комбинаций кода с мощностью кодового алфавита, равной α (в главе 1 применялся символ k), и длиной кодовых слов, равной n,
, (3.1)
где Mр – множество рабочих комбинаций кода (комбинаций, используемых для кодирования сообщений),
, (3.2)
где m = [log Mр]; [x] – ближайшее целое, большее х; m – число информационных символов кода. Тогда (n – m) определяет число избыточных символов k, а (М0 – Мр) – число запрещенных комбинаций кода Мз.
Введем две меры избыточности кода RI и RII (0 ≤ RI, RII ≤ 1):
, (3.3)
. (3.4)
RI – оценка избыточности как доли запрещенных (не используемых для кодирования сообщений) кодовых комбинаций среди всех возможных. Она является точной оценкой избыточности кода, но, к сожалению, редко используется, т. к. n >> 1 и m >> 1 и соответствующие им степени (М0 и Мр) – слишком большие числа.
RII – оценка избыточности как доли разницы между длиной кодовой комбинации n и количеством символов, которые бы понадобились для неизбыточного кодирования Мр сообщений. Она является грубой оценкой избыточности кода, получившая наибольшее практическое применение, т.к. легче иметь дело с показателями степеней, чем с самими степенями.
Величина, обратная RII, для двоичных кодов (α = 2) часто называется скоростью передачи информации (информационной содержательностью) Rи и измеряется в единицах [бит/символ],
Rи = 1 – RII = m / n log2 α = m / n.
3.2. Оценка помехоустойчивости при передаче дискретных сообщений
Введем ряд понятий и обозначений, исследуемых в дальнейшем. Обозначим двоичный n-разрядный кодовый вектор (кодовую комбинацию) через
.
Обозначим n-разрядный вектор ошибки через
.
Ошибка (искажение) в i-м разряде кодового вектора означает подмену одного (передаваемого) кодового символа другим, не равным ему. При этом в i-м разряде вектора ошибки появляется единица.
Обозначим вектор на выходе канала передачи данных (КПД) через . Примем аддитивную модель взаимодействия передаваемого вектора и вектора ошибок (шума), т. е.
. (3.5)
Тогда для двоичного канала ошибка при передаче i-го символа означает его инвертирование. Инверсия двоичного символа эквивалентна выполнению логической операции «исключающее или» («суммирование по модулю два») с логическим символом «1»:
Введем метрику рассматриваемого кодового пространства.
Норма (величина) кодового вектора равна его весу:
где – вес кодового вектора, т. е. число его ненулевых компонентов (разрядов).
Тогда расстояние между двумя кодовыми векторами и
и равно весу разности этих векторов по mod α , т. е.
. (3.6)
При α = 2
. (3.7)
Введенное кодовое расстояние, называемое расстоянием Хемминга, равно числу разрядов, в которых различаются два сравниваемых вектора и .
Пример 3.1. Пусть и , тогда 2;
т. е. два сравниваемых вектора различаются только во втором разряде.
Пример 3.2. Пусть = 1010 и = 0010, тогда = 1000. Следовательно, ошибка произошла в третьем разряде передаваемого вектора, т. к. именно этот разряд вектора ошибки равен 1.
Из (3.5) следует, что
.
Назовем вес вектора ошибки кратностью ошибки. Так, в примере 3.2 w(e) = 1, т. к. имеет место однократная ошибка. Проанализируем события, имеющие место при передаче информации по двоичному симметричному каналу n-разрядным двоичным неизбыточным кодом, для которого справедливо равенство
М0 = М = 2n,
и, следовательно,
RI = RII = 0.
Рассмотрим вероятностные соотношения для передачи сообщений кодовыми комбинациями.
Событие, при котором вся кодовая комбинация принимается правильно, возникает в случае правильного приема всех символов кодовой комбинации. Для симметричного двоичного канала вероятность правильного приема сообщения (отсутствия ошибок) P(0) определяется следующим образом:
(3.8)
где n – длина кодовой комбинации; q – вероятность правильной передачи символа; p – вероятность неправильного (ошибочного) приема одного символа (вероятность ошибки на символ).
Обобщим приведенные соображения, записав вероятность полной группы событий, возникающих при приеме кодовой комбинации. Действительно, возможно одно из следующих событий: нет ошибок – с вероятностью P(0), однократная ошибка в любом разряде – с вероятностью P(1), двукратная ошибка в любых разрядах – с вероятностью P(2), и т. д. Сумма вероятностей, образующих полную группу независимых событий, равна 1:
(3.9)
Рассмотрим, какие могут возникать события после приема кодовых комбинаций кодом неизбыточного кода, т.е. без дополнительных возможностей по повышению достоверности и помехоустойчивости передачи сообщений. Таких событий возможно два:
- правильная передача сообщения – имеет место при правильном приеме всех символов;
- трансформация сообщения – возникает при появлении ошибок, поскольку вместо переданной кодовой комбинации (сообщения) получателю информации будет выдана другая кодовая комбинация (сообщение).
Поскольку указанные варианты образуют полную группу событий, то сумма их вероятностей равна 1. Вероятность правильной передачи Pпр определяется вероятностью P(0), а вероятность трансформации Pтр – суммой всех остальных вероятностей от P(1) до P(n):
(3.10)
Для наглядности анализа указанных событий воспользуемся графом канала передачи данных (ГКПД). При этом на входе дуги находится кодовая комбинация из множества рабочих комбинаций кода {}, а на выходе дуги – кодовая комбинация, наблюдаемая на выходе канала. Это могут быть либо кодовое слово из {} при правильной передаче или трансформации сообщения, либо кодовое слово из множества запрещенных комбинаций кода {} при искаженной передаче. Ребро ГКПД нагружено соответствующим значением вектора ошибки.
Пример 3.3. Пусть М0 = М = 23. ГКПД показан на рис. 3.1.
Рис. 3.1. ГКПД при передаче сообщений неизбыточным кодом n = 3
Из рис. 3.1 видно, что т. к. М0 – М = 0, то подмножество {} – пустое, и, следовательно, любая ошибка вызывает трансформацию сообщения, т.е. является необнаруженной. Действительно, если передается кодовый вектор (кодовая комбинация) = = 100, то искажение (ошибка) в любом разряде вызывает переход в одну из разрешенных комбинаций и получателю выдается другое сообщение.
Таким образом, неизбыточный код не способен обнаруживать ошибки никакой кратности. Возможность кода обеспечить (повысить) достоверность и помехоустойчивость передачи сообщений сводится к наличию у него корректирующих свойств. Они заключаются в том, что даже при наличии некоторого количества ошибок в принятом сообщении трансформации сообщения не возникнет.
Корректирующие свойства кода могут быть направлены на два вида действий:
- исправление ошибок;
- обнаружение ошибок.
Исправление сводится к обнаружению факта наличия ошибок, к определению мест их возникновения (ошибочных разрядов), замене ошибочных символов правильными. Обнаружение сводится только к обнаружению факта наличия ошибок в кодовой комбинации. При этом для недопущения трансформации сообщение с ошибками нужно стереть, а получателя – проинформировать об этом.
Разумеется, процесс исправления ошибок требует более сложного алгоритма обработки и дополнительных затрат, зато более эффективен. Процесс обнаружения ошибок менее требователен к затрачиваемым ресурсам, но и менее эффективен, поскольку требует дополнительных повторов, запросов, подтверждений и т. п. Поэтому он применяется только в системах с обратной связью.
Корректирующие свойства кода могут быть направлены на обнаружение и/или исправление ошибок. Рассмотрим далее общие принципы обнаружения и исправления ошибок корректирующими кодами.
3.3. Обнаружение ошибок избыточными кодами
Рассмотрим структуру избыточного кода (рис. 3.2), обнаруживающего ошибки. В нем выделяются два множества: {} и {}.
Рис. 3.2. ГКПД при передаче сообщений избыточным кодом, обнаруживающим ошибки
Согласно (3.3) избыточность построенного кода .
Покажем, что благодаря введенной избыточности данный код обнаруживает ошибки. Проиллюстрируем с помощью ГКПД передачу сообщений кодом, обнаруживающим ошибки, по ДСК.
Рис. 3.3. ГКПД при передаче сообщений избыточным кодом, обнаруживающим ошибки
Из рис. 3.3 видно, что при передаче сообщений кодом, обнаруживающим ошибки, имеют место три события: правильная передача (неискаженная), трансформация сообщения, вызываемая необнаруженной ошибкой, и стирание сообщения, вызываемое обнаруженной ошибкой. Обнаружение ошибки происходит при появлении на выходе ДСК (на входе декодера) запрещеной комбинации. Доля обнаруживаемых ошибок равна , т. е. совпадает с избыточностью кода.
Пример 3.4. Представим неизбыточный код из примера 3.3 с помощью разбиения рис. 3.2, получив в итоге избыточный код, представленный на рис. 3.4. На этом же рисунке проиллюстрирован и процесс передачи информации.
Рис. 3.4. ГКПД при передаче сообщений избыточным кодом n = 3,
обнаруживающим ошибки нечетной кратности
Разобьем полное множество комбинаций на два непересекающихся множества: множество рабочих комбинаций Мр и множество запрещенных комбинаций Мз. Для первичного кодирования будем использовать только рабочие комбинации Ai.
|
Мр |
Мз |
|||||||
|
A1 |
A2 |
A3 |
A4 |
B1 |
B2 |
B3 |
B4 |
|
|
001 |
010 |
100 |
111 |
000 |
011 |
101 |
110 |
Размерность каждого из множеств равна 4, следовательно,
Проверим корректирующие свойства построенного кода, состоящего из рабочих комбинаци Ai, на примере однократных искажений для любой кодовой комбинации, например A3.
Из приведенного анализа очевидно, что любые однократные искажения переводят комбинацию из множества Мр в множество Мз. Таким образом, ошибка может быть обнаружена путем проверки на принадлежность принятой кодовой комбинации одному из множеств. Для рассматриваемого кода можно оценить корректирующие свойства как способность обнаруживать любые однократные и трехкратные ошибки. Нетрудно убедиться, что двукратные ошибки не могут быть обнаружены, поскольку они оставляют принятую кодовую комбинацию во множестве Мр.
Для исправления ошибки характеристик кода недостаточно. Действительно, любую из комбинаций Bj можно получить в результате ошибки одинаковой кратности в разных рабочих кодовых комбинациях. Например, комбинацию B1 можно получить в результате однократной ошибки e1 в A3, e2 в A2 или e3 в A1.
Кодовые комбинации, принадлежащие множеству запрещенных комбинаций, называют избыточными, поскольку они не используются для первичного кодирования сообщений. Однако, как мы убедились на примере, присутствие избыточных комбинаций в полном множестве кодовых комбинаций является необходимым условием построения кода, корректирующего ошибки.
Избыточность построенного кода оценивается, как RI = 0,5; RII = 0,33. Минимальное кодовое расстояние dmin = 2. Код обнаруживает любые ошибки нечетной кратности. Ошибки четной кратности не обнаруживаются, т.е. вызывают трансформацию сообщений. Можно ввести параметр r как кратность обнаруживаемых ошибок, т.е. код гарантирует обнаружение ошибок кратности не более r.
Рассмотрим вероятностные соотношения при реализации корректирующих свойств кода, направленных на обнаружение ошибок.
Сообщение будет принято правильно, если ошибок в кодовой комбинации нет (вероятность этого события Pпр). Все ошибки кратности не более r будут обнаружены, и сообщение будет стерто (вероятность этого события Pст). Если кратность ошибок превысит r, то произойдет трансформация сообщения (вероятность этого события Pтр).
Запишем сформулированные условия:
Вероятностные соотношения выглядят следующим образом:
(3.11)
Как видно из приведенных соотношений, вероятность транс формации уменьшается из-за появления вероятности стирания.
Очевидно, что для кода, не имеющего корректирующих свойств, избыточность равна 0. Поэтому корректирующие коды еще называют избыточными. Очевидно, что чем больше избыточность, тем выше корректирующие свойства кода. Покажем это, построив код, исправляющий ошибки.
3.4. Исправление ошибок избыточными кодами
Общая структура кода, исправляющего ошибки, представлена на рис. 3.5.
Рис. 3.5. Структура кода, исправляющего ошибки
Для построения кода, исправляющего ошибки, необходимо полное множество М0 комбинаций кода разбить на М непересекающихся подмножеств так, что
, (3.12)
где Li – мощность i-го подмножества запрещенных комбинаций; Li + 1 – мощность подмножества, включая i-ю рабочую комбинацию; данное подмножество называют сигнальной зоной (сферой) i-й рабочей комбинации.
Мощность Li может быть определена как , где S – кратность исправляемых ошибок.
Таким образом, разбиение типа рис. 3.5 удовлетворяет следующим условиям:
Ø ,
. (3.13)
Способ приема состоит в том, что если принята некоторая комбинация из i-го подмножества, то декодером выносится решение о том, что передана комбинация . Таким образом, исправляется та часть всевозможных ошибок, под действием которых i-я рабочая комбинация () не выходит за пределы i-й сигнальной зоны. При этом знак равенства в (3.13) означает, что построен код, исправляющий ошибки, так называемый «плотноупакованный»; знак < означает, что корректирующая способность кода использована либо для исправления ошибок, либо для исправления и обнаружения ошибок. Доля исправляемых ошибок, в предположении, что все рабочие комбинации равновероятны, составляет .
Корректирующая способность избыточного кода должна быть использована для исправления наиболее вероятных ошибок в канале связи. Выполнение этого требования обусловлено конструированием сигнальных зон. Для ДСК, т. е. двоичных симметричных каналов связи, описываемых биномиальным законом распределения ошибок, справедливо соотношение
P(i) > P (i + 1), (3.14)
т.е. ошибки малой кратности более вероятны, чем ошибки большой кратности. Поэтому в i-ю сигнальную зону включаются запрещенные комбинации , удаленные от на наименьшее кодовое расстояние по сравнению с удаленностью от любой другой рабочей комбинации. Тогда оптимальное декодирование исправляющего ошибки кода, учитывающее статистику ошибок в канале связи, будет заключаться в вычислении кодового расстояния от принятого кодового вектора до всех {} и вынесении решения в пользу той рабочей комбинации, до которой кодовое расстояние минимально. Подобная схема принятия решения называется декодированием по критерию максимального правдоподобия, которое считается оптимальным.
Пример 3.5. Построим код, исправляющий однократные ошибки согласно схеме разбиений рис. 3.5.
На рис. 3.6. приведен код с d() = 3, исправляющий все возможные однократные ошибки, и ГКПД, иллюстрирующий процесс передачи информации указанным кодом. Построенный код является плотноупакованным. В КПД имеют место 2 события: правильная передача сообщений и трансформация. Правильная передача имеет место как при отсутствии ошибок, так и при любой однократной ошибке. Из рис. 3.6 видно, что построенный код исправляет любую однократную ошибку, т.к. запрещенная комбинация не выходит из сигнальной зоны соответствующей рабочей комбинации, искаженной однократной ошибкой попутно. Отметим, что сигнальные зоны кода, обнаруживающего ошибки, состоят только из рабочих комбинаций кода, т. е. Li = L = 1, .
Рис. 3.6. Структура избыточного кода n = 3,
исправляющего однократные ошибки и ГКПД
Оценим избыточность кода, исправляющего однократную ошибку.
Минимальное кодовое расстояние dmin = 3.
Еще раз отметим, что чем больше избыточность, тем сильнее корректирующие свойства кода.
Сигнальная зона содержит и кодовые комбинации, которые отличаются от данной рабочей комбинации не более чем в S разрядах, а от остальных рабочих комбинаций – более чем в S разрядах. Поэтому ошибка кратности не более чем S приведет в сигнальную зону переданной рабочей комбинации, что дает возможность для исправления ошибки. При этом ошибки кратности более чем S приведут либо в сигнальную зону другой рабочей комбинации, либо непосредственно в другую рабочую комбинацию, что вызовет трансформацию сообщения. Поэтому можно ввести параметр S как кратность исправляемых ошибок.
Рассмотрим вероятностные соотношения при реализации корректирующих свойств кода, направленных на исправление ошибок.
Будем считать, что все ошибки кратности не более S будут исправлены и сообщение будет принято правильно (вероятность этого события Pпр). Если кратность ошибок превысит S, то произойдет трансформация сообщения (вероятность этого события Pтр). Запишем сформулированные условия:
Вероятностные соотношения выглядят следующим образом:
(3.15)
Как видно из приведенных соотношений, вероятность транс формации уменьшается из-за увеличения вероятности правильной передачи.
3.5. Исправление и обнаружение ошибок избыточными кодами
Рассмотрим избыточные коды, у которых корректирующие свойства направлены на обнаружение и исправление ошибок. Очевидно, что полное множество запрещенных комбинаций содержит подмножество сигнальных зон, предназначенное для исправления ошибок, и подмножество запрещенных комбинаций, предназначенное для обнаружения ошибок. При этом кодовое расстояние до подмножества запрещенных комбинаций больше, чем ширина сигнальной зоны. Это означает, что параметр r для рассматриваемого вида корректирующих кодов всегда больше S.
Пример 3.6. Построим код длины n = 4, исправляющий однократные и обнаруживающий двукратные ошибки.
На рис. 3.7. приведен код с d() = 4, исправляющий все однократные и обнаруживающий все двукратные ошибки, и ГКПД, иллюстрирующий процесс передачи информации указанным кодом. Построенный код является плотноупакованным. В КПД имеют место 3 события: правильная передача сообщений, стирание и трансформация. Правильная передача имеет место как при их отсутствии ошибок, так и при любой однократной ошибке. Стирание происходит при двукратной ошибке. Из рис. 3.7 видно, что построенный код исправляет любую однократную ошибку, т. к. запрещенная комбинация не выходит из сигнальной зоны соответствующей рабочей комбинации, искаженной однократной ошибкой попутно. Двукратные ошибки также будут обнаружены, поскольку переведут рабочую комбинацию во множество запрещенных состояний Мз.
Рис. 3.7. Структура избыточного кода n = 4, исправляющего однократные и обнаруживающиего двукратные ошибки и ГКПД
Оценим избыточность кода, исправляющего однократную и обна руживающего двукратную ошибки.
Минимальное кодовое расстояние dmin = 4.
Рассмотрим вероятностные соотношения при реализации корректирующих свойств кода, направленных на исправление и обнаружение ошибок.
Будем сичтать, что сообщение будет принято правильно, если ошибок в кодовой комбинации нет или кратность ошибок не превышает S, и они будут исправлены (вероятность этого события Pпр). Все ошибки кратности более S и менее r будут обнаружены, и сообщение будет стерто (вероятность этого события Pст). Если кратность ошибок превысит r, то произойдет трансформация сообщения (вероятность этого события Pтр).
Запишем сформулированные условия:
Вероятностные соотношения выглядят следующим образом:
(3.16)
Как видно из приведенных соотношений, вероятность транс формации уменьшается из-за исправления ошибок (увеличения вероятности правильной передачи) и появления вероятности стирания (обнаружения ошибок).
3.6. Геометрическая модель кода
Геометрической моделью n-мерного кода является n-мерный куб, размещенный в n-мерном пространстве. При этом по каждой из n взаимно ортогональных осей откладывается k различных значений ординат, каждая из которых равна одному из k значений соответствующего разряда кода.
Пример 3.7. Рассмотрим геометрическую модель 3-разрядного двоичного кода (рис. 3.8).
Геометрической моделью является 3-мерный куб, каждая из 8 вершин которого соответствует кодовой комбинации двоичного неизбыточного кода. Кружками обведены вершины куба, соответствующие рабочим комбинациям кода, обнаруживающего ошибки из примера 4.4. Каждое ребро куба соответствует расстоянию Хемминга d = 1. На модели видно, что для кода, обнаруживающего ошибки, минимальное расстояние между рабочими комбинациями равно двум (dmin = 2).
Из рис. 3.8 видно, что кодовое расстояние между вершинами куба, соответствующими рабочим комбинациям 101 и 010 (пример 3.5), равно 3.
Рис. 3.8. Геометрическая модель
3-разрядного двоичного кода
Сплошными линиями обведены сигнальные зоны, соответствующие каждой из двух рабочих комбинаций кода, исправляющего однократные ошибки.
3.7. Связь между кодовым расстоянием Хемминга и максимальной кратностью обнаруживаемых и исправляемых ошибок
Обозначим через s максимальную кратность исправляемых ошибок перехода (в дальнейшем – просто ошибок), r – максимальную кратность обнаруживаемых ошибок, ес – максимальную кратность исправляемых ошибок стирания. При использовании обозначения «максимальная кратность» предполагается, что код исправляет либо обнаруживает все ошибки указанной кратности и меньше.
Сформулируем и докажем ряд утверждений.
Утверждение 3.1. Для того чтобы код обнаруживал любые ошибки кратности r и меньше, минимальное кодовое расстояние должно удовлетворять условию
dmin r + 1. (3.17)
Краткое доказательство. Как было показано в подразд. 3.3, сигнальные зоны кода, обнаруживающего ошибки, состоят только из рабочих комбинаций кода. Таким образом, если между комбинациями кода расстояние не меньше r + 1, то не существует никакой ошибки кратности r и меньше, которая перевела бы одну комбинацию кода в сигнальную зону другой (для этого потребуется, по крайней мере, ошибка кратности (r + 1)). Следовательно, все ошибки кратности r и меньше будут обнаружены.
Пример 3.8. Пусть r = 1, поэтому dmin = 1 + 1 = 2. Рассмотрим геометрическое представление кода (рис. 3.9).
Рис. 3.9. Геометрическая иллюстрация
обнаружения ошибки кратности r = 1
Рабочие комбинации Vi и Vj имеют dij = dmin = 2, а кодовое расстояние до любой из комбинаций множества Mз равно d = 1. Поэтому при любой однократной ошибке будет принята кодовая комбинация из Mз. Это даст возможность обнаружить однократную ошибку. При двукратной ошибке вместо одной рабочей комбинации Vi будет принята другая рабочая комбинация Vj. Это приведет к трансформации сообщения.
Код с dmin = 2 был рассмотрен в примере 3.4, из которого видно, что не существует ни одной ошибки нечетной кратности, способной вызвать трансформацию (см. рис. 3.4), т.к. любая такая ошибка переведет рабочую комбинацию кода в запрещенную и будет обнаружена. Но так как двукратные ошибки при этом обнаружены не будут, то код с dmin = 2 в соответствии с утверждением 3.1 гарантирует обнаружение однократных ошибок.
Пусть r = 2, поэтому dmin = 2 + 1 = 3. Рабочие комбинации Vi и Vj имеют dij = dmin = 3, а кодовое расстояние d до любой из комбинаций множества Mз равно 1 или 2. Поэтому при любой однократной или двукратной ошибке будет принята кодовая комбинация из Mз. Это даст возможность обнаружить такие ошибки. При трехкратной ошибке вместо одной рабочей комбинации Vi будет принята другая рабочая комбинация Vj. Это приведет к трансформации сообщения.
Распространив приведенные соображения по закону математической индукции для произвольного значения r, можно считать утверждение доказанным.
Утверждение 3.2. Для того чтобы код исправлял любые ошибки кратности s и меньше, минимальное расстояние должно удовлетворять условию
dmin 2s + 1. (3.18)
Краткое доказательство. В сигнальную зону каждой рабочей комбинации кода, кроме рабочей комбинации, входят еще запрещенные комбинации, удаленные от рабочей на расстояние s и меньше. Согласно условию (3.13) сигнальные зоны не должны пересекаться. Для обеспечения этого условия достаточно соблюдение (3.18), т. к. непересекающиеся сигнальные зоны каждой рабочей комбинации разделяются по крайней мере одним кодовым переходом. Таким образом, при соблюдении (3.18) любая ошибка кратности s и меньше не способна перевести передаваемую рабочую комбинацию в чужую сигнальную зону и, следовательно, в соответствии с правилом принятия решения (п. 3.4) будет исправлена.
Пример 3.9. Пусть s = 1, тогда согласно (3.18) dmin = 3. В примере 3.5 рассмотрен подобный код. Из рис. 3.6 и 3.8 видно, что dmin = 3 гарантирует соблюдение условий (3.18), т. е. сигнальные зоны (СЗ) двух рабочих комбинаций кода не пересекаются. Каждая сигнальная зона состоит из всех возможных запрещенных комбинаций, удаленных от рабочей на d = 1, что соответствует однократным искажениям, и, значит, любая однократная ошибка будет исправлена.
Рассмотрим геометрическое представление кода (рис. 3.10).
Рис. 3.10. Геометрическая иллюстрация исправления ошибки кратности s = 1
Рабочие комбинации Vi и Vj имеют dij = dmin = 3, а кодовое расстояние до любой из комбинаций собственной сигнальной зоны СЗ равно d = S = 1. Поэтому при любой однократной ошибке будет принята кодовая комбинация из СЗ. Это даст возможность исправить ошибку, заменив комбинацию из СЗ на соответствующую ей рабочую комбинацию. При двукратной ошибке будет принята комбинация из сигнальной зоны другой рабочей комбинации. Это приведет к исправлению другой рабочей комбинации и, соответственно, трансформации сообщения. Таким образом, код с
dmin = 3 гарантирует исправление однократной ошибки.
Распространив приведенные соображения по закону математической индукции для произвольного значения s, можно считать утверждение доказанным.
Утверждение 3.3. Для того чтобы код исправлял ошибки кратности s и обнаруживал ошибки кратности от s + 1 до r (s < r), минимальное расстояние должно быть не меньше чем s + r + 1, т. е.
dmin s + r + 1. (3.19)
Краткое доказательство. Проанализированная в утверждении 3.2 конструкция сигнальных зон кода, исправляющего s-кратные ошибки, согласно условию (3.19) требует расстояния между сигнальными зонами, равного по крайней мере 2s + 1.
Пусть r = s + ( 1). Тогда (3.19) гарантирует выполнение требования (3.18), т.е. ошибки кратности s и меньше будут исправлены. При этом ошибки кратности s < r' r = s + ( 1) порождают запрещенные комбинации кода, не принадлежащие ни одной сигнальной зоне. Они удалены от соответствующей рабочей комбинации на кодовое расстояние больше s, в то же время они не переведут рабочую комбинацию в чужую сигнальную зону, т. е. будут обнаружены.
Пример 3.10. Пусть s = 1, r = 2, тогда dmin = 4.
Изобразим фрагмент геометрической модели кода, состоящий из двух рабочих комбинаций: и , таких, что d(,) = 4 (рис. 3.11).
Рис 3.11. Фрагмент геометрической модели кода с dmin = 4
Образуем сигнальные зоны, удовлетворяющие условию (3.13), т.е. непересекающиеся и состоящие из рабочей комбинации и запрещенных комбинаций, удаленных от рабочей на d = 1. Следовательно, такой код исправляет любую однократную ошибку. В то же время любая двукратная ошибка переведет или в запрещенную комбинацию из множества Мз, отличного от обеих сигнальных зон. Применив процедуру оптимального декодирования и установив, что d(Мз ) = 2, можно обнаружить ошибку и стереть сообщение.
При трехкратной ошибке будет принята комбинация из сигнальной зоны другой рабочей комбинации. Это приведет к исправлению другой рабочей комбинации и, соответственно, трансформации сообщения.
Распространив приведенные соображения по закону математической индукции для произвольного значения s и r, можно считать утверждение доказанным.
В зависимости от минимального кодового расстояния корректирующая способность кода может быть перераспределена на разные действия.
|
dmin |
Корректирующие свойства кода: |
|
1 |
|
|
2 |
|
|
3 |
|
|
4 |
|
|
5 |
|
Избыточность вносится в код на передающей стороне и не зависит от корректирующих свойств кода, поскольку определяется только dmin. Очевидно, что корректирующие свойства кода реализуются при процедуре декодирования.
3.8. Верхние и нижние границы избыточных кодов
Верхними границами обычно называются наилучшие граничные соотношения между кодовым расстоянием, числом избыточных и информационных символов, обеспечивающие наименьшую избыточность кода или наибольшую скорость передачи информации. Обсуждаемые ниже верхние границы Хемминга и Плоткина не гарантируют существование кодов с параметрами, полученными из границ. В то же время рассматриваемая нижняя граница Варшамова–Гильберта гарантирует существование кодов с числом избыточных символов, не превышающим некоторую верхнюю оценку избыточных символов при заданных требованиях к dmin.
3.8.1. Верхняя граница Хемминга
Проанализируем соотношение (3.13). Если принять, что
, (3.20)
то указанное соотношение можно записать в виде MрL M0 – Mр.
Обозначим через Е полное множество исправляемых ошибок. Тогда имеет место Е = L. Подставляя (3.1) и (3.2) в (3.20), получим
. (3.21)
Поскольку s – максимальная кратность исправляемых ошибок, то для двоичных n-разрядных кодов, исправляющих ошибки,
. (3.22)
Подставляя (3.22) в (3.21), получим окончательный вид границы Хемминга для двоичных кодов:
. (3.23)
Напомним, что m – число информационных символов кода, n – общее число символов (разрядов) кода, называемое длиной кода, k = (n – m) – число избыточных символов кода. Поделив левую и правую части неравенства (3.23) на 2m, получим другой вид границы Хемминга:
. (3.24)
Неравенства (3.23) и (3.24) при заданных m и s решаются подбором.
Пример 3.11. Найти параметры кода, исправляющего однократную ошибку, для передачи М = 11 сообщений.
Найдем m = [log 11] = 4; s = 1. Тогда из (3.23) получим
.
Подбором устанавливаем, что n = 7; k = 3.
Пример 3.12. Положим, что надо найти все параметры кода длины n = 63 с кодовым расстоянием dmin = 5 и наибольшим возможным значением m – числа информационных символов. Согласно (3.24) получим , kmin [log22017] = 11.
Таким образом, из границы Хемминга следует, что не существует кода с числом избыточных символов k меньше 11 или с числом информационных символов m больше 52. В то же время из замечания, сделанного в начале данного подраздела, о том, что граница Хемминга не является границей существования, следует, что не гарантируется существование кодов с найденными параметрами k = 11, m = 52.
Если для некоторого кода верхняя граница Хемминга выполняется со знаком равенства, то код называется совершенным. Совершенные коды называют также плотноупакованными кодами (см. подразд. 3.4). В заключение отметим, что верхняя граница Хемминга дает точные оценки при больших значениях n.
3.8.2. Верхняя граница Плоткина
В области малых значений верхняя граница Хемминга является довольно грубой. При малых значениях Rи точнее границы Хемминга является верхняя граница Плоткина, определяемая для двоичного
n-разрядного кода следующим образом:
,
где Мр – фактическое число используемых кодовых слов.
. (3.25)
Другой вид границы Плоткина:
mmax n – 2dmin + 2 + log2dmin. (3.25а)
Пример 3.13. Пусть m = 4, dmin = 3. Тогда из (3.25) получим и n 5,625. Выбираем ближайшее большее целое число n = 6, тогда согласно (3.25,а) mmax 4 и k ≥ 2.
Таким образом, из границы Плоткина следует, что не существует кода, исправляющего однократные ошибки, с числом избыточных символов k меньше 2 и общей длиной кода меньше 6. Действительно, ближайший существующий код с максимальной скоростью передачи имеет параметры n = 7, k = 3. Но данный пример подтвердил, что граница Плоткина дает лучшие оценки, чем граница Хемминга, при малых Rи. Данный пример подтверждает, что граница Плоткина не является границей существования. В работе [10] показано, границы Плоткина достигают лишь коды, в которых расстояние между любыми двумя различными кодовыми словами одно и то же; такие коды называются эквидистантными. Например, двоичными эквидистантными кодами являются коды, состоящие из последовательностей максимальной длины, и коды, получающиеся из матриц Адамара [10,11]. Наряду с рассмотренными верхними границами существует еще граница Элайеса, которая лучше обеих рассмотренных границ, по крайней мере при средних скоростях . Граница Элайеса нами не рассматривается.
Отметим, что в главе 5, посвященной алгебраическим кодам, в частности групповым систематическим кодам, нами будет использована верхняя граница Хемминга (3.24).
3.8.3. Нижняя граница Варшамова–Гильберта
Как отмечалось выше, наряду с верхними границами существуют нижние кодовые границы, в частности граница Варшамова–Гильберта [12]. Сравнительный анализ этих границ показывает следующее. Верхняя граница утверждает, что не существуют коды с числом избыточных символов меньше определенного граничного числа k1. В то же время нижняя граница, в частности Варшамова–Гильберта, «гарантирует» существование кодов с числом избыточных символов k2 меньше другого граничного числа: k2 > k1.
Нижняя граница Варшамова–Гильберта имеет вид
. (3.26)
При этом утверждается, что существует (n,m)-код с кодовым расстоянием, не меньшим d, и с числом избыточных разрядов k ≤ n – m.
Пример 3.14. Оценим с помощью границы Варшамова–Гильберта параметры кода из примера 3.12, т.е. кода длины n = 63 с dmin = 5. Согласно (4.21) имеем или . Тогда наименьшее число избыточных символов k, для которого выполняется это неравенство, … 16.
Итак, сравнивая результаты примеров 3.12 и 3.14, приходим к такому выводу: из границы Хемминга следует, что не существует кодов с k < 11, т.е, по Хэммингу, k 11 (нижняя граница по избыточным символам и, следовательно, верхняя граница по информационным символам), а граница Варшамова–Гильберта «гарантирует» существование кодов с k 16 (верхняя граница по избыточным символам и, следовательно, нижняя граница по информационным символам).
3.9. Оптимальное декодирование с «жестким» и «мягким» принятием
решения первой решающей схемой
В главе 2 описан поэлементный прием сигналов ПРС, получивший наибольшее распространение в современных цифровых телекоммуникационных системах. ПРС может принимать «жесткое» и «мягкое» решение относительно элементарных сигналов на входе. Если мощность входного канального алфавита равна k, а мощность выходного канального алфавита , то условно такой канал обозначим как ()-канал. Тогда при «жестком» принятии решения имеет место , а при «мягком» – .
Мы будем рассматривать (2 )-канал, т. е. двоичный симметричный канал, у которого мощность выходного канального алфавита больше трех. Промежуточное место между поэлементным приемом с «жестким» принятием решений и «приемом в целом» занимает прием с «мягким» принятием решения. Было доказано, что в (2 )-канале нецелесообразно делать больше 8, т. е. 8 [12]. Поэтому ниже будет рассмотрен (2 8)-канал. Выигрыш в помехоустойчивости канала передачи данных, оцениваемый разными критериями, обусловлен при «мягком» декодировании, по сравнению с «жестким» декодированием, объемом дополнительной информации о величине искаженного элементарного сигнала, поступающего на вход декодера.
3.9.1. Сигнальные зоны, реализуемые в ПРС (2 8)-канала
Пусть ПРС реализует когерентный прием двух противоположных сигналов . В канале действует «белый шум» со спектральной плотностью . Оптимальным приемником является согласованный фильтр (СФ) с импульсной характеристикой , где Т – длительность элементарного сигнала, на который настроен согласованный фильтр. Отсчеты сигналов на выходе СФ берутся с частотой следования сигналов и подаются на вход решающего (регистрирующего) устройства (РУ). В ПРС с «жестким» принятием решения РУ определяет знак отсчета, т. е. сигнальные зоны противоположных сигналов отслеживают только знак входного сигнала. В ПРС с «мягким» принятием решения сигнал с выхода СФ подается на вход аналого-цифрового преобразователя с N уровнями квантования (N = 8). Таким образом, РУ принимает решение о величине сигнала на его входе, и на вход декодера передается одно из восьми соответствующих значений элементарного сигнала. Значения напряжения на выходе СФ в моменты отсчетов являются гауссовскими случайными величинами со средним значением (в зависимости от передачи 1 или 0) и дисперсией 2 = (Es – энергия принятого элементарного сигнала). Таким образом, плотность распределения вероятностей напряжения на выходе согласованного фильтра (рис. 3.12) имеет вид
. (3.27)
Рис. 3.12. Плотность распределения вероятностей значения напряжения
Шкала квантования сигналов на выходе СФ равномерная с шагом квантования
. (3.27)
Величина j-го квантованного отсчета на выходе РУ
, (3.28)
где – весовой коэффициент.
Опуская количественные оценки обоснования выбора , минимизирующие вероятность ошибки на выходе ПРС, приведем оптимальное распределение весовых коэффициентов в (2 8)-канале [12]: {} = {0, 3, 6, 9, 12, 15, 18, 21}.
В дальнейшем изложении для упрощения расчетов , т.е. кодового расстояния, реализуемого оптимальным декодером в канале
2 8, примем другое распределение весовых коэффициентов: {} = {0, 1, 2, 3, 4, 5, 6, 7}.
При использовании простого аналого-цифрового преобразователя двоичный симметричный канал преобразуется в симметричный канал с двоичным входом и восьмеричным выходом, т. е. в (2 8)-канал. Переходные вероятности в симметричном (2 8)-канале вычисляются как площади под графиком плотности распределения вероятностей между соответствующими уровнями квантования :
, (3.29)
где – условная вероятность появления на выходе РУ ПРС квантованного сигнала величины Uj при передаче символа «0». При этом с учетом свойства симметрии справедливо соотношение
, (3.30)
где– максимальное число уровней квантования, включая нулевой.
Из (3.30) для сигнальных зон S0 и S1 получим
Этот ряд можно продолжить и для вероятностей ошибок перехода. Граф (2 8)-канала приведен на рис. 3.13.
Рис. 3.13. Граф симметричного (2 8)-канала
3.9.2. Оптимальное декодирование в канале с «мягким» принятием решения
Для вычисления кодового расстояния в канале с «мягким» принятием решения введем метрику, отличную от (3.6):
, (3.31)
где .
Пример 3.15. Пусть = (3, 4, 0, 7, 7, 7) и = (1, 7, 1, 3, 4, 5). Тогда 2 + 3 + 1 + 4 + 3 + 2 = 15.
В канале с «жестким» принятием решения по-прежнему пользуемся метрикой (3.6).
Алгоритм оптимального декодирования по критерию максимального правдоподобия, реализуемый декодером в канале 2 8 с «мягким» принятием решения, таков:
1. В памяти декодера хранятся все (2m – 1)-векторов. При этом для двоичной записи каждого символа отводим по три ячейки памяти.
2. Для исправления ошибок при приеме вектора вычисляются по формуле (3.31) кодовые расстояния , где . Находится наименьшее кодовое расстояние . Декодер принимает решение о том, что передавался кодовый вектор .
3. Для исправления и обнаружения ошибок при приеме вектора повторяется процедура, описанная в п. 2. Если для некоторого находится наименьшее кодовое расстояние среди всех вычисленных, то принимается решение о том, что передавался вектор . Если же хотя бы для двух хранимых кодовых векторов и вычисленные кодовые расстояния до совпали, т. е. =, то сообщение стирается.
Пример 3.16. Рассмотрим код с параметрами n = 7, m = 3, dmin = 4. В двоичном симметричном канале с «жестким» принятием решения данный код исправляет однократные ошибки (некоторые сочетания двукратных ошибок – при оптимальном декодировании) и обнаруживает все двукратные ошибки и ряд ошибок большей кратности. Проанализируем корректирующую способность этого же кода, но в канале 2 8 с «мягким» принятием решения (см. рис. 3.12 и 3.13). Представим два из семи векторов рассматриваемого кода: и соответственно в каналах с «жестким» и «мягким» принятием решения.
В канале 2 2:
В канале 2 8:
Рассмотрим несколько ситуаций, различающихся величиной и кратностью ошибки (степенью искажения) при передаче вектора :
1. Возникла двукратная ошибка во втором и третьем символах (подчеркнуты).
Решение в пользу , т.е. двукратная ошибка исправлена.
2. . Возникла двукратная ошибка, но увеличилась величина искажения.
= 10; = 18. Решение в пользу , т.е. и эта двукратная ошибка исправлена.
3. . Произошла двукратная ошибка с максимальной величиной искажения.
= 14; = 14. В соответствии с описанным выше алгоритмом принято решение о стирании сообщения.
Данный пример подтверждает, что в канале с «мягким» принятием решения в целом возрастает корректирующая способность кода, полностью реализуемая оптимальным декодером. Это обусловлено дополнительной информацией о величине ошибки (степени искажения), выдаваемой ПРС декодеру (за счет усложнения ПРС).
3.9.3. Оптимальное декодирование в двоичном канале со стиранием
Наиболее часто применяются следующие модели двоичного канала:
- канал с «жестким» принятием решения (канал 2 2);
- канал с «мягким» принятием решения (канал 2 3) (канал со стиранием).
При «жестком» приеме для передаваемого символа возможны два варианта приема – правильный и ошибочный. Для двоичного канала связи ошибочный прием эквивалентен инверсному значению символа. Размерность алфавита на входе и выходе канала связи совпадает (рис. 3.14).
Рис. 3.14. Модель ошибок канала с «жестким» принятием решения
Вероятности P00 и P11 соответствуют правильному приему символа, а вероятности P01 и P10 – неправильному (ошибочному или инверсному) приему символа (вероятность ошибки).
В рассматриваемой модели имеют место следующие вероятностные соотношения:
(3.32)
С точки зрения соотношения вероятностей ошибки разных направлений ранее были введены понятия симметричный и асимметричный канал. Для симметричного канала вероятности ошибок разных направлений совпадают, а для асимметричного – отличаются. Для симметричного двоичного канала связи вводились следующие обозначения:
(3.33)
где p – вероятность ошибочного приема символа; q – вероятность правильного приема символа.
Большинство каналов связи описывается именно моделью симметричного канала связи с уверенным приемом (жестким принятием решения). Однако существуют ситуации, когда эффективно применение модели канала с «мягким» принятием решения. Размерность алфавита на выходе таких каналов связи больше, чем на входе, за счет появления дополнительных символов. Эти символы характеризуют некоторые значения принятых сигналов, по которым символ нельзя отнести ни к одному из алфавита на передающей стороне (неуверенный прием). Например, для двоичного канала 2 3 вводится дополнительный символ «х» (рис. 3.15). Подобные каналы, реализуемые ПРС, называются каналами со стиранием.
Рис. 3.15. Модель ошибок канала со стиранием
Вероятности P00 и P11 соответствуют правильному приему символа, вероятности P01 и P10 – неправильному (ошибочному, инверсному) приему символа (вероятность ошибки), вероятности P0х и P1х – неуверенному приему символа.
В рассматриваемой модели имеют место следующие вероятностные соотношения:
(3.34)
Назовем ошибку, которая возникает при замене одного символа другим, ошибкой перехода. Тогда ошибку, которая возникает при замене символа на «х», назовем ошибкой стирания (удаления символа). На основании вышеназванного введем для симметричного канала связи следующие обозначения:
(3.35)
где pп – вероятность ошибочного приема символа; pс – вероятность стирания символа; q – вероятность правильного приема символа.
На рис. 3.16 и 3.17 изображены примеры для приема сигнала амплитудно-импульсной манипуляции («0» – отсутствие импульса, «1» – импульс с амплитудой Um) в каналах с «жестким» и «мягким» принятием решения.
Рис. 3.16. Иллюстрация приема в канале с «жестким» принятием решения
Рис. 3.17. Иллюстрация приема в канале с «мягким» принятием решения
При уверенном приеме (рис. 3.16) множество возможных значений информационных параметров сигнала разбивается на подмножества, количество которых совпадает с разновидностью символов (размерностью алфавита на входе канала). Для двоичного канала связи таких подмножеств два: зона уверенного приема символа «0» и зона уверенного приема символа «1». Пороговое значение для принятия решения обычно определяется как Um/2.
При неуверенном приеме (рис. 3.17) добавляется зона, в которую попадают значения информационных параметров, которые нельзя отнести ни к одному из символов. Она имеет границы от нижнего порога (Uпн) до верхнего порога (Uпв). Попадание в зону неуверенного приема приводит к замене принятого символа на символ «x». Попадание в зону выше Uпв приводит к принятию решения о приеме символа «1». Попадание в зону ниже Uпн приводит к принятию решения о приеме символа «0».
При уверенном приеме сигнала (символа) из линии связи на выходе ПРС, реализующей «жесткое» принятие решения, наблюдается один из двух символов: «0» и «1». При неуверенном приеме сигнала (символа) из линии связи на выходе ПРС, реализующей «мягкое» принятие решения, наблюдается один из трех символов: «0», «1», «х» (рис. 3.18).
Рис. 3.18. Прием и декодирование линейного сигнала S′(t) в канале со стиранием
Поскольку ошибка стирания обнаруживается уже на уровне ПРС, то для ВРС коррекция ошибок стирания сводится только к исправлению ошибок указанного вида. Количество стираний (символов «х» в принятой кодовой комбинации) явно указывает кратность ошибок стирания.
Сформулируем несколько утверждений, связывающих избыточность (dmin) и корректирующие свойства кода в канале со стиранием.
Утверждение 3.4. Для того чтобы код исправлял любые ошибки стирания кратности ec и меньше, минимальное кодовое расстояние должно удовлетворять условию
dmin еc + 1. (3.36)
Краткое доказательство. Необходимо применить оптимальное декодирование по критерию min кодового расстояния в уверенно принятых символах. Это означает, что нужно вычислить d({Vi},V') и принять решение в пользу того вектора Vi (), для которого d(Vi,V') = 0. Это вытекает из условия, что в уверенно принятых символах отсутствуют ошибки перехода, следовательно, min {d(Vi,V')} = 0 (ошибки стирания исправлены).
Пример 3.17. Выберем избыточный код (7,3,4). dmin = 4, поэтому согласно (3.36) ec = 3. Проведем анализ для рабочих векторов V1 = 1110100 и V2 = 0111010. Пусть принят вектор V' = 11xxx00. Определяем кодовое расстояние по уверенно принятым символам: d(V1,V') = 0, d(V2,V') = 2. По результатам вычислений делаем вывод о том, что был передан вектор V1.
Исправление ошибок стирания сводится к выбору правильного варианта замены символов «x». Аналогичные выводы позволяют сформулировать соотношения для кодов, исправляющих или обнаруживающих и ошибки перехода, и ошибки стирания.
Утверждение 3.5. Для того чтобы код обнаруживал любые ошибки перехода кратности r и меньше и исправлял любые ошибки стирания кратности ес и меньше, минимальное кодовое расстояние должно удовлетворять условию
dmin r + eс + 1. (3.37)
Краткое доказательство. Необходимо применить оптимальное декодирование по критерию min кодового расстояния в уверенно принятых символах. Это означает, что нужно вычислить d({Vi},V') для уверенно принятых символов и принять решение. Если присутствуют только ошибки стирания, то решение принимается в пользу того вектора Vi (), для которого d(Vi,V') = 0. Это вытекает из условия, что в уверенно принятых символах отсутствуют ошибки перехода, поэтому min {d(Vi,V')} = 0. Если присутствуют и ошибки перехода, и ошибки стирания, то все вычисленные кодовые расстояния будут больше нуля (d({Vi},V') >0). По этому условию ошибки будут обнаружены, а сообщение стерто.
Пример 3.18. Выберем избыточный код (7,3,4). dmin = 4, поэтому согласно (3.37) r = 1 и ec = 2 (как один из вариантов). Проведем анализ для рабочих векторов V1 = 1110100 и V2 = 0111010. Пусть принят кодовый вектор V' = 11x1x00. Определяем кодовое расстояние по уверенно принятым символам: d(V1,V') = 1, d(V2,V') = 2. По результатам вычислений делаем вывод об обнаружении ошибок перехода и стирании сообщения.
Утверждение 3.6. Для того, чтобы код исправлял любые ошибки перехода кратности s и меньше и любые ошибки стирания кратности ес и меньше, минимальное кодовое расстояние должно удовлетворять условию
dmin 2s + eс + 1. (3.38)
Краткое доказательство. Необходимо применить оптимальное декодирование по критерию min кодового расстояния в уверенно принятых символах. Это означает, что нужно вычислить d({Vi},V') для уверенно принятых символов и принять решение. Если присутствуют только ошибки стирания, то решение принимается в пользу того вектора Vi (), для которого d(Vi,V') = 0. Это вытекает из условия, что в уверенно принятых символах отсутствуют ошибки перехода, поэтому min {d(Vi,V')} = 0. Если присутствуют и ошибки перехода, и ошибки стирания, то все вычисленные кодовые расстояния будут больше нуля (d({Vi},V') >0). При этом выбирается минимальное кодовое расстояние (для исправления ошибок оно будет s). По этому условию ошибки перехода будут исправлены, а сообщение передано получателю.
Пример 3.19. Выберем избыточный код (7,3,4). dmin = 4, поэтому согласно (3.38) s = 1 и ec = 1. Проведем анализ для рабочих кодовых векторов V1 = 1110100 и V2 = 0111010. Пусть принят кодовый вектор V' = 1111x00. Определяем кодовое расстояние по уверенно принятым символам и получаем d(V1,V') = 1 = s, d(V2,V') = 2 > s. По результатам вычислений делаем вывод об исправлении ошибок перехода и передаче правильного сообщения получателю.
Утверждение 3.7. Для того чтобы код обнаруживал любые ошибки перехода кратности r и меньше, исправлял любые ошибки перехода кратности s и меньше и любые ошибки стирания кратности ес и меньше, минимальное кодовое расстояние должно удовлетворять условию
dmin s + r + eс + 1. (3.39)
Декодирование кодов при наличии ошибок указанной кратности рассмотрено в примерах 3.17, 3.18, 3.19 отдельно, поэтому рассматриваться не будет.
Методы обеспечения помехоустойчивости на приеме в ПРС сводятся к оптимальному приему сигналов на фоне помех. Но для обеспечения высокой достоверности указанных методов явно недостаточно. Это объясняется возможными искажениями в передаваемом по линии связи закодированном сообщении. Обработка кодовых комбинаций происходит во второй решающей схеме. Поэтому методы обеспечения помехоустойчивости при обработке кодовых комбинаций во ВРС сводятся к применению специальных алгоритмов декодирования.
Контрольные вопросы к главе 3
- Привести выражения и сравнить способы оценки избыточности (RI, RII), привести примеры: а) М0 = 16, Мр = 8; б) М0 = 16, Мр = 3.
- Ввести понятия «кодовый вес», «кодовое расстояние» («расстояние Хэмминга»), «кратность ошибки», привести примеры их вычисления. Рассмотреть аддитивную модель воздействия ошибок на кодовый вектор в дискретном канале связи, привести примеры искажения кодового вектора для ошибок кратности e = 1, 2, 3.
- Проанализировать, какие события могут возникать на выходе канала связи при передаче сообщений неизбыточным кодом, привести вероятностные характеристики.
- Проанализировать, какие события могут возникать на выходе канала связи при передаче сообщений избыточным кодом, способным обнаруживать ошибки, привести вероятностные характеристики.
- Проанализировать, какие события могут возникать на выходе канала связи при передаче сообщений избыточным кодом, способным исправлять ошибки, привести вероятностные характеристики.
- Проанализировать связь минимального кодового расстояния с кратностью обнаруживаемых ошибок перехода.
- Проанализировать связь минимального кодового расстояния с кратностью исправляемых ошибок перехода.
- Привести примеры использования корректирующих свойств кода для dmin = 6 и dmin = 7.
- Проанализировать верхние и нижние границы избыточных кодов.
- Рассмотреть оптимальное декодирование в двоичном канале со стиранием, привести вероятностные характеристики.
- Проанализировать связь минимального кодового расстояния с кратностью корректируемых ошибок перехода и стирания.
2. Исполнительная власть в РФ
3. Й ГЛАВЫ ВТОРОГО ПОСЛАНИЯ К СОЛУНЯНАМ 2я глава Второго послания к Солунянам содержащая учение апостол
4. химические элементы и их соединения а также закономерности которым подчиняются различные хим
5. Методы оценки инвестиционного проекта
6. Стратегия социально - экономического развития России
7. Бухгалтерський облік загальна теорія Одеса ОНПУ ~ 2012 МІНІСТЕРСТВО ОСВІТИ
8. новому- в маленьком доме на острове Оркас она занималась воспитанием собак и участвовала в работе Поисковос
9. s for George Soros himself his exceptionl tlent for prediction which won him billions on bets ginst mjor nd lesser world currencies lso turned him to prophet of doom.html
10. реферат дисертації на здобуття наукового ступеня кандидата педагогічних наук Київ 2004
11. Варіанти- а. Процес пов~язаний з історією розвитку цивілізації- древній світ античний світ середньовіччя.
12. Реферат- История развития вычислительной техники
13. Лабораторная работа 3
14. Строение глаза 5 2
15. Защита продовольствия и фуража от ядерного поражения
16. Армения в XI-XIV веках
17. тема живлення карбюраторних двигунівРозділ- Технічні науки Система живлення карбюраторних двигунів Карб
18. Спеціальні економічні зони та їх роль в залученні іноземних інвестицій
19. Тема- Методология педагогической науки Установите соответствие между методологическими характеристик
20. Тема II Планирование аудита налогообложения 2