Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

 

Сверточные коды (СК) имеют большой научный и практический интерес для современных систем и сетей телекоммуникаций. Это определяется многими их достоинствами, а именно:

1. высокой скоростью обработки информации (десятки и сотни Мбит/с),

2. высокой корректирующей способностью как случайных, так пакетных ошибок,

3. реализацией эффективных кодеков,

4. эффективным применением в каналах связи с фазовой неопределенностью и др.

 

В общем виде кодирование информации СК может быть представлено следующим образом:

(1)

 где I(x) – последовательность передаваемых информационных символов; x – формальная переменная; g(x) – порождающий, или образующий, полином (многочлен); k₀ – блок информационных символов, одновременно поступающих на вход кодирующего устройства (k₀ ).

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

 

Рис. 1. Обобщенная структура кодера СК

 

Входные информационные символы I(x) делятся на k₀ символов, которые одновременно с каждым тактом поступают на входы кодера СК, в котором согласно (1) формируются кодовые символы n₀. Таким образом, кодовая последовательность Т⁽ⁱ⁾(x) представляет собой полубесконечную последовательность блоков n₀.

Существенное отличие СК от ЛБК: для ЛБК проверочные символы зависят от одного информационного блока, а для СК проверочные символы зависят как от информационных символов на входе, так и от некоторого количества предшествующих.

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

К основным параметрам СК относятся:

 1.  и т.д. – скорость передачи кода, которая для СК записывается в виде дроби;

2. l= n₀- k₀ – абсолютная избыточность;

3. r=( n₀- k₀)/ n₀ ×100%=(1- R) ×100% – относительная избыточность;

4. J≥2 – количество ортогональных проверочных уравнений, т.е. количество ненулевых членов в образующем полиноме;

5. d₀=J+1 – минимальное кодовое расстояние;

6.  – кратность или количество исправляемых ошибок;

7.  – кратность обнаруживаемых ошибок;

8. n_A =(m+1)n₀ – длина кодового ограничения, или длина кодовой последовательности, соответствующая кодированию информационных блоков из k₀ символов в течение (m+1) такта; m – старшая степень ненулевого многочлена порождающего полинома;

9. k_A =R ×n_A – количество информационных символов, приходящихся на n_A кодовых символов;

10. n_E=J²/2+J/2+1 –эффективная длина кодового ограничения (количество двоичных символов, непосредственно участвующих в декодировании).

 

Классификация СК.

- По основанию кода: двоичные и недвоичные;

- В зависимости от используемого математического аппарата: алгебраические и неалгебраические;

- По алгоритму формирования проверочных символов: линейные и нелинейные;

- По способу передачи: систематические и несистематические;

- По структуре кодовой последовательности: разделимые и неразделимые;

- По алгоритму декодирования: ортогональные и неортогональные;

- По способу преобразования входных информационных символов k₀ в кодовые символы СК являются непрерывными.

 

В зависимости от способа формирования проверочных уравнений СК бывают ортогональными, самоортогональными и ортогонализируемыми.

Ортогональными СК (ОСК) называют такие коды, в которых система из J (J 2) проверочных уравнений ортогональна относительно декодируемых k₀ информационных символов и неортогональна относительно информа­цион­ных символов, входящих в данные проверочные уравнения.

Самоортогональные СК (ССК) – коды, в которых декодируемый инфор­ма­ци­он­ный символ входит одновременно во все проверочные уравнения, а все осталь­ные символы, участвующие в декодировании в данный момент времени, входят не более, чем в одно проверочное уравнение, т.е. СК формирует так называемую, систему раздельных проверок.

Ортогонализируемыми СК называются такие коды, у которых при деко­ди­ро­ва­нии информационного или k₀ символов требуется выполнить допол­ни­тель­ные линейные преобразования над проверочными символами для получения дополнительных, так называемых составных проверок.

 

Задание систематических сверточных кодов

 

Систематические СК задаются:

I. с помощью порождающей матрицы – G_¥(х);

II. с помощью проверочной матрицы – H_¥(х);

III. с помощью разностных треугольников;

IV. с использованием совершенных разностных множеств.

 

I. Задание систематических СК с помощью порождающей матрицы G _¥(х)

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

где "0" - области матрицы, состоящие полностью из нулевых двоичных символов,

т - количество порождающих матриц вида

где – коэффициенты равны либо 1, либо 0.

 

Систематический ССК задаются следующей порождающей матрицей G _¥(х):

 

 

II. Задание систематических СК с помощью проверочной матрицы H _¥(х)

 

Проверочная матрица Н _¥ (х) СК, как и порождающая матрица, является полубес­ко­нечной:

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

Порождающая и проверочная матрицы СК, как и у линейных кодов, связаны выражением: G _¥(х) ×H^T _¥(х)= H _¥(х) ×G^T _¥(х) =0.

 Для систематического ССК с алгоритмом порогового декодирования проверочная матрица H _¥ задается следующим образом:

 

 

(n₀-k₀) строк

Из данной проверочной матрицы следует, что для ССК с  проверочная матрица Н ¥(х) содержит (n₀–k₀) строк и k₀ столбцов проверочных треугольников. Для ССК с , n₀= 2;3; …, проверочная матрица Н ¥(х)содержит k₀=1, т.е. один столбец и n₀ строк проверочных треугольников.

 

Каждый из проверочных треугольников Н ^D_i,_k0+i, i=1,2, …; k₀=1,2, …, проверочной матрицы Н _¥ (х)  общем случае имеет вид:

,

где q – коэффициенты, равные либо 1, либо 0; j, i – номера соответственно строки и столбца матрицы Н_¥(х), которыми определяется проверочный треугольник; 0, …m – порядковые номера степеней, в которые возводятся соответствующие коэффициенты порождающего полинома.

Основную информацию о самоортогональных сверточных кодах ССК несут коэффициенты левого столбца и нижней строки проверочного треугольника.

Пример: задан проверочный треугольник:

 

По данному проверочному треугольнику можно определить параметры ССК с алгоритмом ПД:

1. Поскольку задан один проверочный треугольник, то k₀=1, n₀=k₀+1=2,.  r=( n₀- k₀)/ n₀ ×100%=(1- R) ×100%=50%.

2. Так как k₀=1, то ССК задается одним порождающим полиномом, определяемым коэффициентами левого столбца и нижней строки проверочного треугольника.

g(x)=1+x²+x⁶+x⁷

3. Количество ненулевых членов порождающего полинома определяет число проверочных уравнений: J=4. Следовательно, ССК может исправлять  ошибки и обнаруживать  ошибки.

d₀=J+1=4+1=5

4. Строки проверочного треугольника, которые начинаются с ненулевых двоичных символов, формируют проверочные уравнения, размеры данных проверок и номера позиций информационных и проверочных символов, участвующих в формировании проверочных уравнений. Размеры проверок в проверочном треугольнике обозначены цифрами перед стрелками и определяются количеством ненулевых символов в строке. Для данного примера имеем:

s₀=е₀ⁱ+e₀^p (i– информационный символ, р – проверочный)

s₂=е₀ⁱ+e₂ⁱ+e₂^p

s₆=е₀ⁱ+e₄ⁱ+e₆ⁱ+e₆^p

s₇=е₀ⁱ+e₁ⁱ+e₅ⁱ+e₇ⁱ+e₇^p

5. Длина кодового ограничения n_A и эффективная длина кодового ограничения n_e СК равны, соответственно,

n_A =(m+1)n₀=(7+1)2=16 двоичных символов;

=8+2+1=11 двоичных символов.

На практике наибольшее применение получили два способа построения проверочных треугольников:

- с помощью разностных треугольников

- с помощью совершенных разностных множеств.

 

III . Задание систематических СК с помощью разностных треугольников

 

Разностный треугольник представляет собой совокупность целых, действи­тель­ных и неповторяющихся чисел, записанных в форме треугольника. Для ССК с R = k₀/n₀ количество разностных треугольников равно числу k₀. Для всех разностных треугольников общим числом является “0”, который не указывается в совокупности чисел, однако учитывается при выборе степеней ненулевых членов порождающих полиномов. Степени ненулевых членов порождающих полиномов по заданным или построенным разностным тре­уголь­ни­кам можно найти путем выбора чисел:

· левого крайнего столбца разностного треугольника, считывая их сверху вниз и дополняя числом “0”,

· верхней строки разностного треугольника в такой последовательности: первое число – показатель степени второго ненулевого члена порождающего полинома; суммирование первого и второго чисел первой строки разностного треугольника определяет показатель степени третьего ненулевого члена порождающего полинома и т.д.

Пример: Определить параметры ССК с алгоритмом ПД при следующем разностном треугольнике:

 

 

1. Так как задан один разностный треугольник, то k₀=1, n₀=k₀+1=2, , код имеет один порождающий полином.

2. Выписывая числа левого крайнего столбца разностного треугольника, определяем показатели степеней порождающего полинома: (0,2,6,7). Следо­ва­тель­но, порождающий полином ССК имеет вид: g(х)=1+x²+x⁶+x⁷. При втором способе –0; 2; 2+4=6; 2+4+1=7. Как правило, в литературе разностные треугольники табулированы и представлены, например, так: ((2,4,1), (3,5,2)). Это означает, что ССК имеет соответственно параметры: k₀=2, n₀=k₀+1=3, и g₁(x)=1+x²+x⁶+x⁷ и g₂(x)=1+x³+x⁸+x¹⁰.

Разностный треугольник ССК может быть построен, если задан прове­роч­ный треугольник, и наоборот.

Пример: По проверочному треугольнику построить разностный.

Числа крайнего левого столбца разностного треугольника определяются как результат операции вычитания порядковых номеров строк проверочного треугольника, которые начинаются с “1”. Для первого столбца получаем следующие числа: 3–1=2 (3 – номер позиции третьей строки, 1 – номер позиции первой строки); 7–1=6 и 8–1=7. Для получения чисел второго столбца за вычитаемое берем номер позиции третьей строки: 7–3=4 и 8–3=5. Для получения чисел третьего столбца за вычитаемое берем номер позиции седьмой строки: 8–7=1.

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

 

V. Задание систематических СК с использованием

 совершенных разностных множеств

 

Совершенное разностное множество – это совокупность целых, дей­стви­тель­ных и неповторяющихся чисел d₁, d₂, … d _x, причем d₁< d₂< d _x и разности этих чисел  полученных по некоторому mod x ( x ¹2), также образующих совокупность целых, действительных и неповторяющихся чисел.

Данную совокупность полученных разностных чисел можно использовать в качестве исходных чисел для формирования разностных треугольников и выбора соответствующих порождающих полиномов ССК.

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

Рассмотрим построение ССК с алгоритмом ПД с использованием совер­шен­ных разностных множеств.

Пусть, например, имеется совокупность b=3-х целых, действительных и неповторяющихся чисел (b=1,2,3) и эта совокупность образует b²+ b=3²+3=12 разностей по модулю b²+ b+1=3²+3+1=13, которые равны следующим числам:

1 – 0º1	12 – 8º4	2 – 8º7	0 – 3º1
3 – 1º2	0 – 8º5	8 – 0º8	1 – 3º11
3 – 0º3	8 – 2º6	8 – 12º9	0 – 1º12

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

 

1	2	6	4
3	8	10	5
9	12	11	7

.

j

 

Каждый из столбцов данного множества можно использовать для построения разностного треугольника. Следовательно, можно построить k₀=4 разностных треугольника и четыре ССК с , с J=4 и с с J=5, разбив данное множество на три подмножества.

 Отметим, что с использованием теории совершенных разностных множеств были рассчитаны и табулированы показатели степеней ненулевых членов порождающих полиномов ССК с   для J=2…16.