Будь умным!


У вас вопросы?
У нас ответы:) SamZan.ru

Тема 5. КОДИРОВАНИЕ В ЦСПИ продолжение Введение 5

Работа добавлена на сайт samzan.ru: 2016-03-13


ПОМЕХОУСТОЙЧИВЫЕ КОДЫ ПРИМЕНЯЕМЫЕ В ЦСПИ

Лекция  № 15

Программные вопросы лекции

Тема №5. КОДИРОВАНИЕ В ЦСПИ (продолжение)

Введение

5.7. Кодирование и декодирование систематических кодов

5.8. Циклические коды

Заключение

Литература

Л1. Авиационные радиосвязные устройства. / Под. ред. Тихонова В.И. - М.: ВВИА им. проф. Н.Е. Жуковского, 1986, с. 171…184.

Л2. Величкин А.И., Азаров Г.С., Саютин Ю.В. Средства связи и передачи данных ВВС. – М.: ВВИА им. проф. Н.Е. Жуковского, 1985, с. 125…132.

Л4. Егоров М.П. Теоретические основы и принципы построения радиотехнических систем передачи информации. Часть II. Учебное пособие.- Тамбов: ТВАИИ, 2003, с.22…41.

Наглядные пособия и приложения

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

Лекция №15

Тема №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

                 _______________

                                 R(x) = 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)




1. Макроэкономическая политика как инструмент монетарной стабилизации
2. Реферат- Устройство, работа, неисправности, ремонт сцепления атомобиля КамАЗ
3. управленческих и правовых дисциплин НЕГОСУДАРСТВЕННЫЕ СТРУКТУРЫ УПРАВЛЕНИЯ Программа курса
4. Использование Интернет-ресурсов на уроках английского языка
5. а. Техника постановки зонда Блэкмора- Зонд Блэкмора вводят через нос
6. К договорам применяются правила о двух или многосторонних сделках
7. Повреждения позвоночник
8. Инструментальные средства Microsoft Office
9. тема работы Руководитель преподаватель кафедры А
10. либо явлении или предмете увлекательней приключенческих романов
11. Реферат- Кондорсе про основні епохи історичного процессу
12. Финансирование инвестиций в инфраструктуру рекреационного комплекса
13. Тема 7- Оценка фактического питания подсчет калорий основного обмены использование эскиздиета.
14. Пласти Дип Дойчланд ГмбХ Германия Областиприменения- Погружное и обмазывающее жидкое резиновое покры
15. . Теоретические аспекты инфляции и ее последствия.
16. ___________2012 Планконспект урока по физической культуре и здоровья ’1 Для учащихся 11Б класса Задачи урок
17. Тема- Корень слова.
18. Высотные данные SRTM против топографической съемки
19. В Беспалов В
20. тематическое восприятие объекта