Размещено на http://www.allbest.ru/

2

ОЦЕНКА ХАРАКТЕРИСТИК СУЖЕННОГО КОДА ПРИ ОБРАБОТКЕ КОДОВЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ СИСТЕМ СВЯЗИ С ПЕРЕСПРОСОМ

ХАБИБУЛИН Н.Ф.

The way of mistakes localization on the basis of not constructive runned over method is presented in article. Characteristics narrowed codes are received.

суженный код декодирование ошибка

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

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

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

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

В [1, 2] представлены основные направления комплексной процедуры обработки протоколов ARQ: проводится описание способов запрета части кодовых слов на приемной стороне путем локализации ошибок и введения дополнительных связей в каскадные схемы декодирования.

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

Коды, получаемые путем выбрасывания, рассматривались в [3, 4]. Любой циклический код, порожденный многочленом g(x), может быть сужен до циклического кода путем умножения порождающего многочлена g(x) на дополнительный множитель. Наиболее распространенное сужение [5] дает переход от g(x) к g(x)(x-1). В двоичном случае при этом получается подкод, состоящий из всех слов четного веса исходного кода. Обычно минимальный вес суженного кода на единицу больше минимального веса исходного кода, однако, возможны случаи, когда минимальный вес суженного кода сохраняется или превосходит минимальный вес исходного кода более чем на 1. В работах [3, 4] исследовались границы надежности при выбрасывании кодовых слов достаточно малого веса из случайно выбранного кода. Подобно методу расширения кодов, который также очень полезен при неконструктивном исследовании границ, метод сужения кодов, за исключением тривиальных случаев, не может быть конструктивно использован в алгебраической теории кодов [5].

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

В результате выбрасывания из кода C всех кодовых слов, информационная часть которых не является кодовым словом кода D, получается суженный код B с кодовыми словами из C.

Кодовое слово канального кода C

Кадр ARQ - кодовое слово внешнего кода D

Рисунок 1 - Каскадная схема код D - код C

Поскольку кодовое слово систематического блокового (n, k)-кода состоит из информационной части i(x) и R[i(x)x^n-k]-остатка от деления i(x)x^n-k на порождающий многочлен g(x), то процедура формирования c_B(x)-кодового слова кода B может быть описана следующим образом:

Если c_D(x) = i(x)x^n-k + R_gD(x) [i(x)x^n-k] - кодовое слово (n, k)-кода D,

c_C(x) = i(x)x^N-K + R_gC(x) [i(x)x^N-K] - кодовое слово (N, K)-кода C, тогда

c_B(x) = (i(x)x^n-k + R_gD(x) [i(x)x^n-k]) x^N-K + R_gC(x) [(i(x)x^n-k + R_gD(x) [i(x)x^n-k]) x^N-K]- кодовое слово (N, K)-кода B.

Оценку эффективности предлагается проводить путем сравнения характеристик кодов C и B по следующим параметрам:

- по вероятности ошибки после декодера (Р_ош);

- по вероятности необнаруженной ошибки (Р_НО).

Вероятность ошибки после декодера (Р_ош) однозначно определяется кодовым расстоянием и вероятностью ошибки символа в канале р [6]:

Р_ош = ( C)pⁱ(1-p)^N-i , (1)

где Т=(d-1)/2; Р_ош - вероятность того, что в канале на длине слова N произойдут ошибки весом, более чем T; d - кодовое расстояние. В этом случае декодер произведет ошибочное исправление.

Как видно из формулы (1), Р_ош функционально зависит от Т - максимального количества исправляемых декодером ошибок, которое в свою очередь зависит от кодового расстояния. Исключение векторов из кода С, информационная часть которых не является кодовыми словами кода D, не всегда приводит к увеличению кодового расстояния.

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

Согласно [7] для кода C при вероятности ошибки в канале р вероятность необнаруженной ошибки определяется как:

Р(С,p)_НО= _ipⁱ (1-p)^N-i, (2)

где А_i - количество слов веса i; Р(С,p)_НО - вероятность необнаруженной ошибки кода C при вероятности ошибки символа в канале р.

Для оптимизации процесса вычисления весовых коэффициентов А_i целесообразно применить тождество Мак-Вильямс, устанавливающее связь между распределением весов линейного кода и распределением весов дуального ему кода [8]. Тождество Мак-Вильямс справедливо для любого линейного кода, так как оно вытекает из векторной структуры линейного кода и из того факта, что дуальный коду С код является ортогональным дополнением C.

Пусть А_L и B _L ( L = 0,1,2,3,..,N ) представляют собой распределения весов линейного (n, k) кода и его дуального кода соответственно. В этом случае тождество Мак-Вильямс будет представлено в следующем виде [8]:

B_L=_k A_i P_L( i ), (3)

где Р_L( i ) = _i^k C _n-i^l-k - полином Кравчука, определяемый рекуррентным соотношением [8]:

P_L( i )=P_L-1( i ) - P_L-2( i ) , (4)

с начальными условиями Р₀ ( i ) = 1; P₁ ( i ) = N - 2i.

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

P (B,p)_НО= _ipⁱ(1-p)^N-i , (5)

где B_i - количество слов веса i.

Следует заметить, что декодер, реализующий декодирование кода B, может состоять из двух декодеров: канального кода C и кода D, обнаруживающего ошибки. Простейшим дополнением, превращающим два декодера в один, для кода B будет реализация обратной связи от декодера-D к декодеру-C, по которой могут быть переданы команды на переспрос, запрещающие неправильное решение о кодовом слове канального декодера. Однако, в качестве платы за простоту реализации будет некоторое увеличение вероятности необнаруженной ошибки.

Вероятность необнаруженной ошибки (Р_НО) при совместной работе декодеров внутреннего и внешнего кода находится следующим образом [10]:

Р(D,C,p)_НО= а_Jp^J(1-p)^N-J, (6)

где а_J = B_iN_t(i,j), В_i - элементы весового спектра кода В, который представляет собой кодовую конструкцию внешнего и внутреннего кодов, N_t( i , j ) - число слов веса j находящихся на расстоянии t от кодового слова весом i.

Результат, полученный в [9], позволяет утверждать, что для некоторых систем ARQ, введение дополнительного канального кода, исправляющего ошибки, к коду, обнаруживающему ошибки, в некоторых случаях ухудшает вероятность необнаруженной ошибки.

Переборным методом автором получены характеристики каскадных конструкций для некоторых коротких кодов D и C. Результаты расчетов приведены в таблице 1.

Таблица 1 - вероятности необнаруженной ошибки и ошибки декодирования СС с ARQ для различных кодовых конструкций

Анализ полученных результатов (табл.1) показывает, что при сравнении характеристик кодов C и B вероятность ошибки после декодера (Р_ош), определяемая кодовым расстоянием, не во всех случаях (конструкция (4,3)-(7,4)) показывает эффективность применения кода B. Объяснением этого является то, что минимальное расстояние хотя и характеризует корректирующие возможности кода, но не раскрывает их полностью. Большинство кодов с расстоянием d позволяет исправлять не только все ошибки кратности d/2, но и многие ошибки более высокой кратности. Оказывается возможным исправлять столь много ошибок кратности, большей чем d/2, что вероятности отказа от декодирования и ошибки декодирования существенно меньше, чем вероятность того, что в канале произойдет более d/2 ошибок.

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

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

Для большинства кодов, включая и большинство БЧХ-кодов, при использовании полного алгоритма декодирования вычислить вероятность ошибки декодирования очень трудно. При таком алгоритме декодирование происходит правильно всякий раз, когда вектор ошибки является лидером смежного класса. Для большинства кодов распределение весов лидеров смежного класса мало изучено [5]. С неконструктивной точки зрения последняя задача больше поддается решению.

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

ЛИТЕРАТУРА

1. Хабибуллин, Н.Ф. Повышение исправляющей способности полиномиальной проверки путем локализации ошибок [Текст] // Н.Ф. Хабибуллин / Вестник ИКСИ, Серия "Р", №1 (15), Москва, АФСБ, 1998 год, С. 147-157.

2. Хабибуллин, Н.Ф. Комплексная процедура обработки протоколов обнаружения ошибок и переспроса [Текст] // Н.Ф. Хабибулин, А.А. Проскурин, М.В. Докукин / Сборник научных трудов ВИПС №8, Орел, ВИПС, 1998. С.48-57.

3. Шеннон, К., Вероятность ошибки для оптимальных кодов в гауссовском канале [Текст] / К. Шеннон,сб. «Работы по теории информации», М., 1963.

4. Галлагер, Р.Г. Простой вывод теории кодирования и некоторые применения [Текст] / Р.Г. Галлагер / Кибернетический сборник, новая серия, вып.3, «Мир», М. 1966.

5. Бэрлекэмп, Э. Алгебраическая теория кодирования [Текст]: [пер. с англ. И. И. Грушко]/ Э. Бэрлекэмп, под ред. С. Д. Бермана. М., «Мир», 1971.

6. Злотник, Б.М. Помехоустойчивые коды в системах связи [Текст] / Б.М. Злотник, - М.: Радио и связь, 1989.- 232 с.

7. Блейхут, Р. Теория и практика кодов, контролирующих ошибки [Текст] / Р. Блейхут, - М.: Мир, 1986.

8. Мак-Вильямс, Ф.Дж. Теория кодов, исправляющих ошибки. [Текст]: [пер. с англ. И. И. Грушко и В. А. Зиновьева]/ Ф.Дж. Мак-Вильямс, Н. Слоэн; под ред. Л. А. Бассалыго.- М., «Связь», 1979.

9. Клеве, Т. Обнаружение ошибок после декодирования кода с исправлением ошибок [Текст] / Т. Клеве, М. Миллер / IEEE Trans. Inform. 27, 1981.

10. Витерби, А.Д. Принципы цифровой связи и кодирования [Текст] / А.Д. Витерби, Дж.К. Омура / М., Радио и связь, 1982.

Размещено на Allbest.ru