Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ПОМЕХОУСТОЙЧИВЫЕ КОДЫ ПРИМЕНЯЕМЫЕ В ЦСПИ
Лекция № 15
Программные вопросы лекции
Тема №5. КОДИРОВАНИЕ В ЦСПИ (продолжение)
Введение
5.7. Кодирование и декодирование систематических кодов
5.8. Циклические коды
Заключение
Литература
Л1. Авиационные радиосвязные устройства. / Под. ред. Тихонова В.И. - М.: ВВИА им. проф. Н.Е. Жуковского, 1986, с. 171…184.
Л2. Величкин А.И., Азаров Г.С., Саютин Ю.В. Средства связи и передачи данных ВВС. – М.: ВВИА им. проф. Н.Е. Жуковского, 1985, с. 125…132.
Л4. Егоров М.П. Теоретические основы и принципы построения радиотехнических систем передачи информации. Часть II. Учебное пособие.- Тамбов: ТВАИИ, 2003, с.22…41.
Наглядные пособия и приложения
Плакаты, поясняющие принципы формирования систематических и циклических кодов, плакат с образующими полиномами циклических кодов.
Тема №5. КОДИРОВАНИЕ В ЦСПИ (продолжение)
В предыдущих лекциях были рассмотрены принципы построения, классификация и основные характеристики помехоустойчивых кодов. Эти сведения позволяют составить общее представление о процедуре помехоустойчивого кодирования. С учетом этого, можно более углубленно рассмотреть конкретные варианты построения различных по своей структуре помехоустойчивых кодов.
В настоящее время для повышения помехоустойчивости передачи цифровых сигналов часто применяются систематические и циклические коды. В соответствии с принципами, заложенными в данных двух методах кодирования, строятся кодеры каналов современных ЦСПИ.
5.7. Кодирование и декодирование систематических кодов
Как уже указывалось выше, в систематических кодах информационные символы при кодировании не изменяются, а проверочные символы получают в результате суммирования по модулю 2 определенного числа информационных символов. Запишем разрешенную кодовую комбинацию систематического (n,k) – кода в виде
, (5.9)
где - множество информационных символов, а - множество проверочных символов. Тогда значение любого проверочного символа можно представить как
, , (5.10)
где - весовые коэффициенты, принимающие значение 1 или 0 в зависимости от того, участвует или нет данный информационный символ aj в формировании проверочного символа bi
Обнаружение и исправление ошибок систематическим кодом сводится к определению и последующему анализу синдрома или вектора ошибок. Под синдромом понимают совокупность символов , сформированных путем сложения по модулю 2 принятых проверочных символов и вычисленных проверочных символов :
Вычисленные символы получаются из принятых информационных символов по тому же правилу (5.10), которое используется для их формирования.
Если при приеме информационных и проверочных символов не произошло ошибок, то принятые и вычисленные проверочные символы будут равны. В этом случае все разряды синдрома будут представлены нулями. Таким образом, нулевой синдром соответствует случаю отсутствия ошибок. Если в принятой комбинации есть ошибки, то в разрядах синдрома появятся единицы. Это и есть способ обнаружения ошибок систематическим кодом. Если код имеет минимальное кодовое расстояние , то он способен исправлять ошибки. Это означает, что по виду синдрома можно определить номер ошибочной позиции в принятой кодовой комбинации. Процедура построения систематического кода, способного обнаруживать ошибки, сводится к выбору весовых коэффициентов в (5.10), таким образом, чтобы синдром, рассматриваемый как двоичное число, указывал номер ошибочной позиции.
Поясним на конкретном примере, как это можно сделать. Пусть требуется построить систематический код длиной , способный исправлять одиночные ошибки. Тогда из неравенства (5.5) находим, что . Пользуясь условием границы Плоткина, находим, что минимально необходимое число проверочных символов . Тогда число информационных символов . Следовательно, необходимо построить код (7,4), кодовые комбинации которого имеют вид
,
а три проверочных символа находятся путем суммирования информационных символов по правилу
;
; (5.12)
.
Найдем весовые коэффициенты . Для этого запишем все возможные трехразрядные кодовые комбинации синдрома: 000; 001; 010; 011; 100; 101; 110; 111 и присвоим их ошибочным символам кодовой комбинации.
Когда в принятой кодовой комбинации нет ошибок, синдром будет состоять из трех нулей:
Появление одной единицы в синдроме связано с ошибками в проверочной части кодовой комбинации:
100 – ошибка в ; 010 – ошибка в ; 001 – ошибка в ,
а появление большего числа единиц связано с ошибками в информационной части.
Присвоим информационным символам с ошибками оставшиеся синдромы в порядке возрастания их двоичных чисел (по существу, безразлично, какие двоичные числа присваивать информационным символам):
011 – ошибка в ; 101 – ошибка в ; 110 – ошибка в ; 111 – ошибка в .
Итак, каждому символу кодовой комбинации соответствует двоичное число, представляющее синдром (таблица 5.1).
Теперь осталось определить весовые коэффициенты в (5.12). Для этого необходимо их подобрать так, чтобы при возникновении ошибки в - символе появлялся соответствующий синдром. Например, для появления синдрома 011 (ошибка в )
весовые коэффициенты при символе в уравнениях (5.12) должны иметь значения . Аналогично, появление остальных синдромов обеспечивают коэффициенты:
101 (ошибка в ;
110 (ошибка в ;
111 (ошибка в .
Окончательно правило формирования проверочных символов (5.12) принимает вид
;
; (5.13)
.
Формирование систематического кода (7,4) по правилу (5.13) поясняется рис.5.12.
Пример. Дана кодовая комбинация 1101. Построить разрешенную кодовую комбинацию систематического кода (7,4) и показать, что данный код исправляет одну ошибку.
Находим проверочные элементы согласно правилу (5.13):
;
;
;
.
Таким образом, разрешенная кодовая комбинация имеет вид
.
Предположим, что произошла ошибка в символе , т.е. была принята кодовая комбинация
.
По принятой кодовой комбинации вычисляем проверочные символы:
;
;
.
Теперь находим синдром
Согласно таблицы 5.1 синдрому 101 соответствует информационный символ . Следовательно, значение принятого символа необходимо исправить, т. е. 0 заменить 1. Таким образом, ошибка исправлена, а кодовая комбинация принята правильно.
5.8. Циклические коды
Циклические коды относятся к классу линейных систематических кодов. Они названы циклическими потому, что циклический сдвиг разрешенной кодовой комбинации приводит также к разрешенной комбинации. Например, если - разрешенная кодовая комбинация, тогда после ее циклической перестановки получим новую кодовую комбинацию , которая также является разрешенной комбинацией циклического кода. Циклическое свойство этих кодов позволило упростить реализацию кодеров и декодеров и дало возможность в системах связи строить эффективные блочные коды большой длины с большим количеством разрешенных кодовых комбинаций. Цикл реализовать сравнительно просто, например, с помощью набора триггеров, объединенных в регистры сдвига.
Сущность циклической перестановки заключается в том, что крайний левый символ кодовой комбинации (символ старшего разряда) занимает место первого, первый – второго и т.д. до тех пор, пока предпоследний символ не займет место последнего. Запишем совокупность кодовых комбинаций, получающихся циклическим сдвигом n-разрядной кодовой комбинации, например пятиразрядной 10011:
10011, 00111, 01110, 11100, 11001.
При работе с циклическими кодами принято кодовые комбинации рассматривать в виде полиномов (многочленов) некоторой степени
,
где x – основание системы счисления; bi – цифры данной системы счисления. Для двоичной системы счисления x=2, а bi равны 0 или 1. Например, двоичную последовательность 010101 можно представить в виде многочлена . Действительно,
;
.
Представление кодовых комбинаций в виде многочленов позволяет установить однозначное соответствие между ними и свести действия над кодовыми комбинациями к действиям над многочленами. Над многочленами можно производить все алгебраические действия. Следует заметить, что при работе с двоичными многочленами сложение осуществляется по модулю два.
Суммирование по модулю два дает такие же результаты, как и вычитание. Поэтому как при умножении полинома на полином, так и при их делении используется основная логическая операция суммирования по модулю два.
Пример. В результате суммирования по модулю двух полиномов
G1(x) = x6+x5+x2+1 и G2(x) = x5+x3 получим G(x) = x6+x3+x2+1.
Для рассмотрения принципа построения циклических кодов введем следующие обозначения: G(x) - полином степени k-1, отображающий кодовую комбинацию первичного кода; P(x) - образующий (порождающий) полином степени r=n-k и F(x) - полином степени n-1, отражающий кодовую комбинацию (кодовое слово) циклического кода.
В качестве разрешенных кодовых комбинаций циклического кода принимаются такие комбинации, которые делятся без остатка на заранее выбранный образующий полином P(x), выбираемый из таблицы порождающих полиномов. Построение циклического кода сводится к определению полинома F(x) для известных G(x) и P(x) при условии, что F(x) делится без остатка на P(x).
Существует два способа получения кодового слова циклического кода.
1. F(x) получается путем прямого перемножения полиномов P(x) и G(x). Однако, при этом образуется неразделимый код, декодирование кодовых комбинаций которого очень сложно (информационные и проверочные знаки неразделимы).
2. Представляем информационную часть кодовой комбинации длиной k в виде полинома G(x).
Далее:
а) умножаем G(x) на одночлен xr и получаем G(x)xr, т. е. производим сдвиг k-разрядной кодовой комбинации на r разрядов;
б) делим многочлен G(x)xr на образующий полином P(x) степень которого равна r;
в) полученный остаток R(x) (очевидно его наивысшая степень равна r-1) складываем по модулю два с G(x) xr и получим, таким образом, разрешенную кодовую комбинацию F(x) = G(x) xr R(x).
Пример. Закодируем циклическим кодом длиной n=10 КК 1110001.
Решение
1). r =n – k = 10 – 7 = 3. Из таблицы образующих полиномов выберем P(x) степени 3
P(x) = x3 +x2+1
2). Исходной кодовой комбинации соответствует полином
G(x) =x6 +x5 + x4 + 1.
3). Умножим полином сообщение на x3
G(x)·x3 =x9 +x8 + x7 + x3.
4). Полученное произведение разделим на образующий полином P(x)
x9 + x8 + x7 + x3 x3 + x2 +1
x9 + x8 + x6 ________________
___________________ x6 + x4 +x
x7 + x6 +x3
x7 + x6 + x4
_________________
x4 + x3
x4 + x3 +x
_______________
Ответ: Полином, отображающий комбинацию циклического кода, будет иметь вид
F(x)= G(x)xr + R(x) = x9+x8+x7+x3+x .
Ему соответствует передаваемая в канал КК циклического кода: 1110001 010.
А. Обнаружение ошибок при циклическом кодировании
Обнаружение ошибок при циклическом кодировании сводится к делению принятой кодовой комбинации на образующий полином, который использовался при формировании кода. Наличие остатка после деления свидетельствует о появившейся ошибке при передаче данного кода.
Б. Исправление ошибок
Остаток от деления свидетельствует о наличии ошибки. Для исправления ошибок (обнаружение места ошибки) необходимо обеспечить условие, при котором количество различных ненулевых остатков равно числу комбинаций из n по t (t- количество ошибок исправляемых кодом). Это означает, например, что с n=15 при t=2 следует иметь С215 =105 остатков, что обеспечивается при r = 7 (27-1=127). Следовательно необходимо выбрать образующий полином с r=7 и код (15,7).
Исправление ошибки рассмотрим на конкретном примере.
Пример. Дан (11,7)-код с Р(0,1)=1001. (Р(0,1) есть образующий полином Р(х), выраженный в кодовой последовательностью 1 и 0-й). Пусть передается разрешенная комбинация
F(0,1) = 10110111100
Предположим, ошибка произошла в старшем разряде, т.е.
F*(0,1) = 00110111100
Для определения одной ошибки введем многочлен ошибки степени n.
E = 10000000000 (т. е. х10)
Разделим принимаемую кодовую комбинацию на образующий полином. То же проделаем с многочленом ошибки (т. е. поделим на образующий полином). Совпадение остатков покажет, что многочлен ошибки выбран правильно и ошибка именно в старшем разряде.
В случае, если ошибка произошла в середине принимаемого кода, остатки R1 и R2 не совпадут. При этом к принимаемой кодовой комбинации F*(0,1) необходимо справа дописать 0 и получить R1 (т.е. сдвинуть последовательность влево). Такой сдвиг осуществлять до тех пор, пока R1 и R2 не будут одинаковыми. Число сдвигов плюс 1 покажет разряд, где произошла ошибка (относительно старшего разряда).
Заключение
Рассмотренные выше помехоустойчивые коды широко используются в современных системах передачи информации. Простейшие помехоустойчивые коды позволяют сравнительно просто реализовать устройства кодирования и декодирования. Систематические и циклические коды обеспечивают большую эффективность функционирование ЦСПИ при обнаружении и исправлении ошибок.
Таблица 5.1
|
Синдром |
Символ кодовой комбинации с ошибкой |
|
000 |
нет ошибок |
|
001 |
b3 |
|
010 |
b2 |
|
011 |
a1 |
|
100 |
b1 |
|
101 |
a2 |
|
110 |
a3 |
|
111 |
a4 |
Разрешенная
кодовая
комбинация (n=7)
Информационные
символы (k=4)
|
a1 |
a2 |
a3 |
a4 |
|
a1 |
a2 |
a3 |
a4 |
b1 |
b2 |
b3 |
Рис.5.12 Формирование систематического кода (7,4)