Сделай Сам Свою Работу на 5

Способы описания циклических кодов

ИССЛЕДОВАНИЕ СИСТЕМ СВЯЗИ

С ИСПОЛЬЗОВАНИЕМ ЦИКЛИЧЕСКИХ КОДОВ

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

Подготовка к выполнению работы

Во время подготовки к лабораторной работе необходимо:

1. Повторить по конспекту лекций, рекомендованной литературе [2, 3] ме­тоды кодирования и декодирования циклическими кодами, характеристики их помехозащищенности и структуры кодеков на примере разделимого систематиче­ ского циклического кода (7,4) с порождающим полиномом g(х) = х3 + х + 1. Кодо­вое расстояние этого кода dтiт = 3.

2. Ответить на контрольные вопросы.

3. Найти все кодовые слова заданного кода.

4. Определить характеристики заданного кода в режиме исправления ошибок:

 

4.1. Определить кратность 4 гарантированно исправляемых кодом ошибок.

4.2. Найти число различных векторов ошибок, исправляемых кодом.

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

4.4. Для одного из векторов ошибок, исправляемых кодом, найдите соответ­ствующий этому вектору синдром. Найдите несколько из возможных векторов ошибок, при декодировании которых получается тот же синдром и, следователь­но, происходит ошибочное декодирование.

4.5.При условии, что кодом в первую очередь исправляются ошибки наи­меньшей кратности, рассчитайте для заданного кода вероятность Раш ошибочного декодирования, если канал является двоичным симметричным каналом без памя­ти (ДСК) с вероятностью ошибки в двоичном символе Ро

Численное значение Ро возьмите из табл. 15.1.

Таблица 15.1 Вероятности ошибки в двоичном символе

0,01 0,1 0,05 0,2 0,02 0,04 0,03 0,06 0,15 0,08

 

5. Определите возможности заданного кода в режиме обнаружения ошибок:

5.1.Определите кратность /t0 гарантированно обнаруживаемых кодом ошибок.

5.2.Найдите векторы ошибок, которые не могут быть обнаружены задан­ным кодом.

5.3. Рассчитайте вероятность Рно необнаружения ошибок заданным кодом в ДСК с вероятностью ошибки в символе Р0.

Краткие сведения из теории линейных циклических кодов

Способы описания циклических кодов

Циклическим кодомназывается линейный блочный (n,m)-код, который характеризуется свойством цикличности, т.е. сдвиг влево на один шаг любого разрешенного кодового слова дает также разрешенное кодовое слово, принадлежащее этому же коду и у которого, множество кодовых слов представляется совокупностью многочленов степени (n-1) и менее, делящихся на некоторый многочлен g(x) степени k=n-m, являющийся сомножителем двучлена xn+1.

Название кода произошло от его свойства, заключающегося в том, что каждая кодовая комбинация может быть получена путем циклической перестановкисимволов комбинации, принадлежащей этому же коду. Это означает, что если кодовая комбинация а0 а1 а2аn-1 является разрешенной комбинацией циклического кода, то комбинация вида аn-1 а0 а1 а2аn-2 так же является разрешенной комбинацией и принадлежит этому коду. Запись а0а1аn-1 означает, что кодовая комбинация состоит из n разрядов, первый из которых а0 , последний аn-1.

Отличие комбинации аn-1 а0 а1 а2аn-2 от комбинации а0 а1 а2аn-1 состоит в том, что последний разряд аn-1 становится первым, а предпоследний аn-2 становится последним. Такая перестановка называется циклической.

Циклические коды часто описываются с использованием многочленов (полиномов) переменной X

X = Р(x); Р(x) = an-1xn-1 + … + a1x+a0, (15.1)

где аi – цифры данной системы исчисления (в двоичной системе 0 и 1). Так, например, двоичное семиразрядное число 1010101 может быть записано в виде полинома:

Р(x) = 1x6 + 0x5 + 1x4 + 0x3 + 1x2 + 0x1 + 1x0 = x6 + x4 + x2 + 1. (15.2)

То есть цифры двоичного кода рассматриваются как коэффициенты многочлена Р(x). Наибольшая степень х в слагаемом с ненулевым коэффициентом называют степенью многочлена (полинома). Представление кодовых комбинаций в виде (15.1) позволяет свести действия над комбинациями к действиям над многочленами. При этом сложение двоичных многочленов сводится к сложению по модулю 2 коэффициентов при равных степенях переменной х

ха + ха = 0 ; ха+0 = ха ; 0 + 0 = 0. (15.3)

Умножение производится по обычному правилу перемножения степенных функций:

(15.4)

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

Циклический сдвиг на один разряд соответствует алгебраическому умножению некоторого многочлена g(x), который выбран в качестве исходного на х. Процесс получения новых комбинаций кода можно представить следующим образом g(x), х g(x), х2 g(x), х3 g(x),…, хn-1 g(x).

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

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

 

 
 

 

 

 


Рис. 15.1. Алгоритм формирования циклического кода

 

Задача состоит в том, чтобы сформировать кодовые комбинации на передаче, удовлетворяющие указанному условию. Метод построения кодовых комбинаций используется следующий. В процессе кодирования многочлен Р(x) отображающий двоичный код передаваемого сообщения (примитивный код) умножаются на хk. При этом длина кодовой комбинации увеличивается на k разрядов. Эти дополнительные разряды будут проверочными. Полученное произведение Р(xxk делят на специально подобранный образующий многочлен g(x). При этом получают остаток R(x). Данный остаток R(x) суммируют с произведением Р(xxk. Получают кодовую комбинацию F(x)= Р(xxk +R(x), которая будет без остатка делиться на g(x).

Алгоритм формирования комбинаций циклического кода показан на рис. 15.1.

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

 

Матричное задание кодов

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

,
где - единичная матрица; - прямоугольная матрица контрольных разрядов.

Строки матрицы определяются из выражений

é ù - остаток от деления на образующий полином ,

где - значение i-той строки матрицы ;

i - номер строки матрицы .

Преимуществами кодирования с помощью образующей матрицы являются:

1) большое быстродействие (не требуются сдвиги кодируемого числа),

2) компактная запись всех комбинаций кода.



©2015- 2017 stydopedia.ru Все материалы защищены законодательством РФ.