Оценка эффективности алгоритмов кодирования в цифровых системах передачи информации



Скачать 57.25 Kb.
Дата27.04.2016
Размер57.25 Kb.
ОЦЕНКА ЭФФЕКТИВНОСТИ АЛГОРИТМОВ КОДИРОВАНИЯ

В ЦИФРОВЫХ СИСТЕМАХ ПЕРЕДАЧИ ИНФОРМАЦИИ
П. В. Мартынов, М. С. Светлов
Саратовский государственный технический университет

имени Гагарина Ю. А., Саратов, Россия


В настоящее время в цифровых системах передачи широкое применение находят циклические коды. Особый интерес представляют коды Боуза-Чоудхури-Хоквингема (БЧХ), являющиеся одними из лучших в классе циклических кодов. Именно эти коды составляют основу каскадного кодирования в передающих устройствах цифровых телерадиовещательных систем стандарта DVB-T2, принятого, вслед за европейскими странами, к внедрению в РФ. В цифровых телерадиовещательных передатчиках коды БЧХ используются как коды так называемого внешнего кодирования. При этом обеспечивается оптимальное соотношение помехоустойчивости и затрат на реализацию устройств кодирования-декодирования [1].

В настоящее время существует ряд алгоритмов процедур кодирования информации с использованием кодов БЧХ. Данная работа посвящена проблеме выбора наиболее эффективных алгоритмов БЧХ – кодирования, с учетом особенностей их реализации в цифровых системах телерадиовещания.

Оценка эффективности алгоритмов кодирования проводится на базе предложенного авторами ранее критерия эффективности. В соответствии с этим критерием вычисляются нормированные коэффициенты эффективности для каждого из анализируемых алгоритмов:

, (1)

где M – объем памяти, необходимый для реализации алгоритма; K – число вспомогательных переменных в структуре алгоритма; V – число ветвлений в структуре алгоритма; N – количество действий, выполняемых в ходе реализации алгоритма (сложность алгоритма); Mэт, Kэт, Vэт, Nэт – эталонные (минимальные из возможных) значения соответствующих критериальных параметров; α, β, γ, δ – целочисленные (для удобства вычислений) положительные весовые коэффициенты, учитывающие «вес» каждого из критериальных параметров.

Будем для простоты считать «веса» параметров в формуле (1) одинаковыми и равными единице:

. (2)

В современных цифровых телерадиовещательных системах наиболее часто для кодирования кодом БЧХ используются следующие алгоритмы работы устройств кодирования:



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

  • определение контрольных разрядов, соответствующих входной информационной последовательности, как остатка от деления полинома, соответствующего входному сигналу, на образующий полином кода (вариант 2);

  • определение контрольных разрядов последовательности по проверочным соотношениям кода, задаваемым его проверочной матрицей (вариант 3).

Вычисление кодовой последовательности согласно варианту 1 алгоритма кодирования описывается формулой:

, (4)

где Sвх — входная последовательность; Sвых — выходная (закодированная) последовательность; G – образующая матрица кода.

Вариант 2 алгоритма кодирования основан на вычислении полинома r(х) остатка от деления полинома Sвх(x), соответствующего входной последовательности, на образующий полином кода g(x):

. (5)

Последовательность, описываемая полиномом остатка r(x), является контрольной для исходной информационной последовательности.

Вариант 3 алгоритма кодирования основан на вычислении контрольных разрядов, исходя из проверочных соотношений, соответствующих каждой из строк проверочной матрицы кода H:

, (6)

где - элементы соответствующих строк проверочной матрицы, занятые единичными символами.

Блок-схемы рассматриваемых вариантов алгоритмов кодирования представлены на рисунках 1-3. При этом: n – длина (разрядность) кода; m – число информационных разрядов кода; k – число контрольных разрядов кода; Sвх – входная последовательность, Sвых – выходная (закодированная) последовательность, G – образующая матрица кода, H – проверочная матрица кода; g(x) – образующий полином кода; h – порядок образующего полинома.

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



  • вариант 1: M1=4+m+n+mn. Для решения оценочной задачи можно принять M1 mn;

  • вариант 2: M2=8+2m+3h+k+n≈2m+3h+k+n≈3m;

  • вариант 3: M3=6+m+n+knkn.

Из анализа полученных выражений следует, что минимальный объем памяти необходим для реализации алгоритма определения контрольной части кода как остатка от деления полинома, соответствующего входной информационной последовательности, на образующий полином кода. Будем считать это минимальное значение эталонным: Mэт=M2=3m. Таким образом, значения коэффициентов эффективности алгоритмов по объему памяти примут вид:





Число вспомогательных переменных, необходимое для реализации каждого из алгоритмов, определяется следующим образом:



  • вариант 1: K1=2;

  • вариант 2: K2=4+2h+mm;

  • вариант 3: K3=3.

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





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



  • вариант 1: V1=2mn+m+n-1≈2mn;

  • вариант 2: V2=2h+2n-m+2k+mh2-h2+3≈mh2;

  • вариант 3: V3=3mk+2m+nk-k-1≈4mk.

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





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



  • вариант 1: N1=20mn+2m+n-3≈20mn;

  • вариант 2: N2=6mh2-6h2+11k-11hm+11m+22h+2n-8≈6mh2;

  • вариант 3: N3=3nk+7mk+8m+3n-k-3≈10mk.

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





Применяя формулу (2), получаем значения комплексных коэффициентов эффективности каждого из алгоритмов:







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


Рис. 1. Блок-схема алгоритма по варианту 1.








Рис. 2. Блок-схема алгоритма по варианту 2.


Рис. 3. Блок-схема алгоритма по варианту 3.


СПИСОК ЛИТЕРАТУРЫ
1. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования / Р. Морелос-Сарагоса, пер. с англ. В.Б. Афанасьева // М.: Техносфера, 2005.


База данных защищена авторским правом ©bezogr.ru 2016
обратиться к администрации

    Главная страница