Двоичные циклические коды - раздел Образование, Теория информации и кодирования Вышеприведенная Процедура Построения Линейного Кода Имеет Ряд Недостатков. Он...
Вышеприведенная процедура построения линейного кода имеет ряд недостатков. Она неоднозначна (МДР можно задать различным образом) и неудобна в реализации в виде технических устройств. Этих недостатков лишены линейные корректирующие коды, принадлежащие к классу циклических.
Циклическими называют линейные (n,k)-коды, обладающие следующим свойством: для любого кодового слова:
;
существует другое кодовое слово:
,
полученное циклическим сдвигом элементов исходного кодового слова ||KC|| вправо или влево, и которое также принадлежит этому коду.
Для описания циклических кодов используют полиномы с фиктивной переменной. Будем обозначать эту переменную буквой Х.
Например, кодовое слово ||KC|| = ||011010|| .
Его можно описать полиномом
А(Х) = 0*Х5+1*Х4+1*Х3+0*Х2+1*Х1+0*Х0 .
Таким образом, разряды кодового слова в описывающем его полиноме используются в качестве коэффициентов при степенях фиктивной переменной Х.
Наибольшая степень фиктивной переменной Х в слагаемом с ненулевым коэффициентом называется степенью полинома. В вышеприведенном примере получился полином 4-й степени.
Теперь действия над кодовыми словами сводятся к действиям над полиномами. Вместо алгебры матриц здесь используется алгебра полиномов.
Рассмотрим алгебраические действия над полиномами, используемые в теории циклических кодов.
Суммирование полиномов разберем на примере С(Х) = А(Х) + В(Х).
Пусть ||A|| = ||011010||, ||B|| = ||110111||.
Тогда:
| A(X)
| =
|
| +
| X4
| +
| X3
| +
|
| +
| X1
| +
|
|
| B(X)
| =
| X5
| +
| X4
| +
|
| +
| X2
| +
| X1
| +
| X0
|
| C(X)
| =
| X5
| +
| 0
| +
| X3
| +
| X2
| +
| 0
| +
| X0
|
Таким образом, при суммировании коэффициентов при Х в одинаковой степени результат берется по модулю 2. При таком правиле вычитание эквивалентно суммированию.
Умножение выполняется как обычно, но с использованием суммирования по модулю 2.
Рассмотрим умножение на примере умножения полинома (Х3+Х1+Х0) на полином (Х1+Х0).
|
|
| Х3
| +
|
| +
| Х1
| +
| Х0
|
|
|
|
|
|
|
| Х1
| +
| Х0
|
|
|
| Х3
| +
|
| +
| Х1
| +
| Х0
|
| Х4
| +
|
| +
| Х2
| +
| Х1
|
|
|
| Х4
| +
| Х3
| +
| Х2
| +
|
| +
| Х0
|
Операция обратная умножению – деление. Деление полиномов выполняется как обычно, за исключением того, что вычитание выполняется по модулю 2 (вспомним, что вычитание по модулю 2 эквивалентно сложению по модулю 2).
Пример деления полинома (Х6+Х4+Х3) на полином (Х3+Х2+Х0):
| Х6
| +
| 0
| +
| Х4
| +
| Х3
| +
| 0
| +
| 0
| +
| 0
| Х3
| +
| Х2
| +
| 0
| +
| Х0
|
| Х6
| +
| Х5
| +
| 0
| +
| Х3
|
|
|
|
|
|
| Х3
| +
| Х2
|
|
|
|
|
|
|
| Х5
| +
| Х4
| +
| 0
| +
| 0
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| Х5
| +
| Х4
| +
| 0
| +
| Х2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 0
| +
| Х2
|
|
|
| .
|
|
|
|
|
|
|
|
Циклический сдвиг влево на одну позицию коэффициентов полинома степени n-1 получается путем его умножения на Х с последующим вычитанием из результата умножения полинома Xn+1, если его порядок n. Последнее эквивалентно вычислению остатка от деления результата умножения на Xn+1.
Проверим это на примере.
Пусть требуется выполнить циклический сдвиг влево на одну позицию коэффициентов полинома С(Х) = Х5+Х3+Х2+Х0.
В результате должен получиться полином = Х4+Х3+Х1+Х0 .
Это легко доказывается:
= С(Х)*Х-(Х6+1)=(Х6+Х4+Х3+Х1)+(Х6+Х0) = Х4+Х3+Х1+Х0 .
В основе циклического кода лежит образующий полином m-го порядка (напомним, что m – число дополнительных разрядов). Будем обозначать его gm(X).
Образование кодовых слов (кодирование) KC выполняется путем умножения информационного полинома (информационный полином – полином с коэффициентами, являющимися информационной последовательностью) Иi(X) порядка i<k на образующий полином:
КСm+i(Х) = gm(X) * Иi(X) .
Принятое кодовое слово может отличаться от переданного искаженными разрядами – результатом действия искажающих передаваемую информацию помех.
ПКС(Х) = КС(Х) + ВО(Х),
где ВО(Х) – полином вектора ошибки, а суммирование, как обычно, ведется по модулю 2.
Декодирование, как и раньше начинается с нахождения опознавателя, в данном случае в виде полинома ОП(Х). Этот полином вычисляется как остаток от деления полинома принятого кодового слова ПКС(Х) на образующий полином gm(X):
.
Первое слагаемое остатка не имеет, т.к. кодовое слово было образовано путем умножения полинома информационной последовательности на образующий полином. Следовательно, и в данном случае опознаватель полностью зависит от вектора ошибки.
.
Образующий полином выбирается таким, чтобы при данном m как можно больше число отношений ВО(Х)/gm(Х) давало различные остатки.
Такому требованию отвечают так называемые неприводимые полиномы, которые не делятся без остатка ни на один полином степени m и ниже, кроме как сам на себя и на 1.
Приведенная здесь процедура образования кодового слова неудобна тем, что такой код получается несистематическим, т.е. таким, в кодовых словах которого нельзя выделить информационные и дополнительные разряды.
Этот недостаток был устранен.
Способ кодирования, приводящий к получению систематического линейного циклического кода, состоит в приписывании к информационной последовательности И дополнительных разрядов ДР.
Эти дополнительные разряды предлагается находить по следующей формуле:
Порядок полинома ДР(Х) гарантировано меньше m (поскольку это остаток).
Приписывание дополнительных разрядов к информационной последовательности, используя алгебру полиномов, можно описать формулой:
KC(X) = И(Х)*Хm + ДР(Х)
Одним из свойств циклических линейных кодов является то, что результат деления любого разрешенного кодового слова КС на образующий полином g также является разрешенным кодовым словом.
Докажем, что получаемые по вышеприведенному алгоритму кодовые слова являются кодовыми словами циклического линейного кода. Для этого нужно убедиться в том, что произвольное разрешенное кодовое слово делится на образующий полином без остатка:
.
Рассмотрим первое слагаемое: ,
где d(X) – целая часть результата деления.
Подставим полученную сумму на место первого слагаемого:
.
Суммирование последних двух слагаемых дает нулевой результат (напомним, что суммирование выполняется по модулю 2).
Значит − целая часть деления. Остатка нет. Это означает, что описанный выше способ кодирования соответствует циклическому коду.
Все темы данного раздела:
Курс лекций
Эффективная организация обмена информации приобретает все большее значение как условие успешной практической деятельности людей. Объем информации, необходимый для нормального функционирования совре
Определение понятия информация
Слово информация происходит от латинского informare – изображать, составлять понятие о чем-либо, осведомлять.
Информация наряду с материей и энергией является первичны
Фазы обращения информации
Система управления состоит из объекта управления, комплекса технических средств, состоящего из компьютера, входящих в его состав устройств ввода-вывода и хранения информации, устройств сбора переда
Некоторые определения
Данные или сигналы, организованные в определенные последовательности, несут информацию не потому, что они повторяют объекты реального мира, а по общественной договоренности о кодировании, т.е. одно
Меры информации
Прежде, чем перейти к мерам информации, укажем, что источники информации и создаваемые ими сообщения разделяются на дискретные и непрерывные. Дискретные сообщения слагаются из конечно
Геометрическая мера
Определение количества информации геометрическим методом сводится к измерению длины линии, площади или объема геометрической модели данного носителя информации или сообщения. По геометрическим разм
Аддитивная мера (мера Хартли)
Аддитивную меру можно рассматривать как более удобную для ряда применений комбинаторную меру. Наши интуитивные представления об информации предполагают, чтобы количество информации увеличивалось пр
Энтропия и ее свойства.
Существует несколько видов статистических мер информации. В дальнейшем будем рассматривать только одну их них ─ меру Шеннона. Мера Шеннона количества информации тесно связана с понятие
Энтропия и средняя энтропия простого события
Рассмотрим подробнее понятие энтропии[1] в разных вариантах, так как оно используется в шенноновской теории информации. Энтропия - мера неопределенности некоторого опыта. В простейшем случае его ис
Метод множителей Лагранжа
Если нужно найти экстремум (максимум, минимум или седловую точку) функции n переменных f(x1, x2, …, xn), связанных k<n условиями зависимости, котор
Вывод формулы среднего значения энтропии на букву сообщения
Предположим, имеется сообщение, состоящее из n букв: , где j=1, 2, …, n ─ номера букв в сообщении по порядку, а i1, i2, … ,in номера букв
Энтропия сложного события, состоящего из нескольких зависимых событий
Теперь предположим, что элементы сообщения (буквы) взаимозависимы. В этом случае вероятность появления последовательности из нескольких букв не равна произведению вероятностей появ
Избыточность сообщения
Как отмечалось, энтропия максимальна, если вероятности сообщений или символов, из которых они составлены, одинаковы. Такие сообщения несут максимально возможную информацию. Если же сообщение имеет
Содержательность информации
Мера содержательности[5] обозначается cont (от английского Content ─ содержание).
Содержательность события I выражается через функцию меры содержательности его о
Целесообразность информации
Если информация используется в системах управления, то ее полезность разумно оценивать по тому эффекту, который она оказывает на результат управления. В связи с этим в 1960 г. советским ученым А.А.
Динамическая энтропия
Здесь энтропия рассматривается как функция времени. При этом преследуется цель – избавиться от неопределенности, т.е. добиться положения, когда энтропия равна 0. Такая ситуация характерна для задач
Энтропия непрерывных сообщений
Исходные данные часто представляются в виде непрерывных величин, например, температура воздуха или морской воды. Поэтому представляет интерес измерение количества содержащейся в таких сообщениях ин
Первый случай (значения сл. величины ограничены интервалом)
Случайная величина a ограничена интервалом [b,c]. В этом случае определенный интеграл ее плотности распределения вероятностей (дифференциального закона распределения вероятностей) на
Второй случай (заданы дисперсия и математическое ожидание сл. величины)
Предположим теперь, что область определения значений случайной величины не ограничена, но задана ее дисперсия D и математическое ожидание M. Заметим, что дисперсия прямо пропорциональ
Квантование сигналов
Непрерывные сигналы – носители информации – представляют собой непрерывные функции непрерывного аргумента – времени. Передача таких сигналов может выполняться при помощи непрерывных каналов связи,
Виды дискретизации (квантования)
Наиболее простыми и часто используемыми видами квантования являются:
· квантование по уровню (будем говорить просто квантование);
· квантование по времени (будем называть
Критерии точности представления квантованного сигнала
В результате обратного преобразования из непрерывно-дискретной формы в непрерывную получается сигнал , отличающийся от исходного на величину ошибки . Сигнал называется воспроизводящей функц
Элементы обобщенной спектральной теории сигналов
Обобщенная спектральная теория сигналов объединяет методы математического описания сигналов и помех. Эти методы позволяют обеспечить требуемую избыточность сигналов с целью уменьшения влияния помех
О практическом использовании теоремы Котельникова
Возможную схему квантования-передачи-восстановления непрерывного сигнала можно представить в виде, изображенном на рис. 2.5.
Рис. 2.5. Возможная схема квантования-передачи-
Выбор периода дискретизации (квантования по времени) по критерию наибольшего отклонения
В результате квантования по времени функции x(t) получается ряд значений x(t1), x(t2), … квантуемой величины x(t) в дискретные моменты времени t
Интерполяция при помощи полиномов Лагранжа
Воспроизводящая функция в большинстве случаев рассчитывается по формуле: , где − некоторые функции. Эти функции обычно стремятся выбрать так, чтобы
. (2.14)
В этом случае ,
Оценка максимального значения ошибки при получении воспроизводящей функции на основе полинома Лагранжа
Найдем погрешность интерполяции. Представим ее виде:
, (2.16)
где K(t) – вспомогательная функция, которую надо найти.
Для произвольного t* имеем:
(
Обобщение на случай использования полиномов Лагранжа произвольного порядка
Интерполяция полиномами n-го порядка рассматривается аналогично предыдущим случаям. При этом наблюдается значительное усложнение формул. Обобщение приводит к формуле следующего вида:
Выбор интервала дискретизации по критерию среднеквадратического отклонения
Рассмотрим случай дискретизации случайного стационарного эргодического процесса x(t) с известной корреляционной функцией . Восстанавливать будем при помощи полиномов Лагранжа. Наиболее часто
Оптимальное квантование по уровню
Рисунком 2.13 иллюстрируется принцип квантования по уровню[7].
Рис. 2.13. Квантование по уровню.
Это квантование сводится к замене значения исходного сигнала уровн
Расчет неравномерной оптимальной в смысле минимума дисперсии ошибки шкалы квантования.
Рис. 2.19. Обозначения
Зададимся теперь числом шагов квантования n, границами интервала (xmin, xmax
Общие понятия и определения. Цели кодирования
Кодирование − операция отождествления символов или групп символов одного кода с символами или группами символов другого кода.
Код (франц. code), совокупность зна
Элементы теории кодирования
Некоторые общие свойства кодов[8].
Рассмотрим на примерах. Предположим, что дискретный источник без памяти, т.е. дающий независимые сообщения – буквы – на выходе, име
Неравенство Крафта
Теорема 1. Если целые числа n1, n2, …, nk удовлетворяют неравенству
, (3.1)
существует префиксный код с алфавитом объемом m,
Теорема 2.
Формулировка. Пусть задан код с длинами кодовых слов n1, n2, … , nk и с алфавитом объема m. Если код однозначно декодируем, неравенство Крафта удовле
Теорема 3.
Формулировка. При заданной энтропии H источника и объеме m вторичного алфавита существует префиксный код с минимальной средней длиной nср min
Теорема о минимальной средней длине кодового слова при поблочном кодировании (теорема 4)
Рассмотрим теперь случай кодирования не отдельных букв источника, а последовательностей из L букв.
Теорема 4.
Формулировка. Для данного дискретного источника
Оптимальные неравномерные коды
Определения.
Неравномерными называют коды, кодовые слова которых имеют различную длину.
Оптимальность можно понимать по-разному, в зависимости о
Лемма 1. О существовании оптимального кода с одинаковой длиной кодовых слов двух наименее вероятных кодируемых букв
Формулировка. Для любого источника с k>=2 буквами существует оптимальный (в смысле минимума средней длины кодового слова) двоичный код, в котором два наименее вероятных сло
Лемма 2. Об оптимальности префиксного кода нередуцированного ансамбля, если префиксный код редуцированного ансамбля оптимален
Формулировка. Если некоторый префиксный код редуцированного ансамбля U'является оптимальным, то соответствующий ему префиксный код исходного ансамбля т
Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.
Рассмотрим алфавит из восьми букв. Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется три символа.
Наибольший эффек
Параметры эффективности оптимальных кодов
Таких параметров 2: коэффициент статистического сжатия и коэффициент относительной эффективности. Оба параметра характеризуют степень уменьшения средней длины кодового слова. При этом средняя длина
Особенности эффективных кодов.
1. Букве первичного алфавита с наименьшей вероятностью появления ставится в соответствие код с наибольшей длиной (лемма 1), т.е. такой код является неравномерным (с разной длиной кодовых слов). В р
Помехоустойчивое кодирование
Как следует из названия, такое кодирование предназначено для устранения вредного влияния помех в каналах передачи информации. Уже сообщалось, что такая передача возможна как в пространстве, так и в
Простейшие модели цифровых каналов связи с помехами
Свойство помехоустойчивых кодов обнаруживать и исправлять ошибки в сильной степени зависит от характеристик помех и канала передачи информации. В теории информации обычно рассматривают две простые
Расчет вероятности искажения кодового слова в ДСМК
Положим, кодовое слово состоит из n двоичных символов. Вероятность неискажения кодового слова, как несложно доказать, равна:
.
Вероятность искажения одного символа (однокра
Общие принципы использования избыточности
Для простоты рассмотрим блоковый код. С его помощью каждым k разрядам (буквам) входной последовательности ставится в соответствие n-разрядное кодовое слова. Количество разного вида
Граница Хэмминга
Граница Хэмминга Q, определяет максимально возможное количество разрешенных кодовых слов равномерного кода при заданных длине n кодового слова и корректирующей способности кода КСК
Избыточность помехоустойчивых кодов
Одной из характеристик кода является его избыточность. Увеличение избыточности в принципе нежелательно, т.к. увеличивает объемы хранимых и передаваемых данных, однако для борьбы с искажениями избыт
Линейные коды
Рассмотрим класс алгебраических кодов, называемых линейными.
Определение: Линейными называют блоковые коды, дополнительные разряды которых образуются
Определение числа добавочных разрядов m.
Для определения числа добавочных разрядов можно воспользоваться формулой границы Хэмминга:
.
При этом можно получить плотноупакованный код, т.е. код с минимальной при заданных пар
Построение образующей матрицы
Линейные коды обладают следующим свойством: из всего множества 2k разрешенных кодовых слов, образующих, кстати, группу, можно выделить подмножества из k слов, обладающих св
Порядок кодирования
Кодовое слово КС получается путем умножения матрицы информационной последовательности ||X|| на образующую матрицу ||OM||:
||KC1*n|| = ||X
Порядок декодирования
В результате передачи кодового слова через канал оно может быть искажено помехой. Это приведет к тому, что принятое кодовое слово ||ПКС|| может не совпасть с исходным ||КС||.
Некоторые свойства циклических кодов
Все свойства циклических кодов определяются образующим полиномом.
1. Циклический код, образующий полином которого содержит более одного слагаемого, обнаруживает все одиночные ошибки.
Построение кода с заданной корректирующей способностью
Существует несложная процедура построения кода с заданной корректирующей способностью. Она состоит в следующем:
1. По заданному размеру информационной составляющей кодового слова длиной
Матричное описание циклических кодов
Циклические коды можно, как и любые линейные коды, описывать с помощью матриц.
Вспомним, что KC(X) = gm(X)*И(Х) .
Вспомним также на примере порядок умножения пол
Выбор образующего полинома
Ясно, что полиномы кодовых слов КС(Х) должны делиться на образующий полином g(X) без остатка. Циклические коды относятся к классу линейных. Это означает, что для этих кодов существует
Виды каналов передачи информации
Рассмотрим каналы, отличающиеся по типу используемых в них линий связи.
1. Механические, в которых для передачи информации используется перемещение каких-либо твердых, жид
Пропускная способность каналов связи
Эта тема является одной из центральных в теории информации. В ней рассматриваются предельные возможности каналов связи по передаче информации, определяются характеристики каналов, влияющие на эти в
Пропускная способность дискретного канала связи с шумом
Исследуем теперь пропускную способность дискретного канала связи с шумом.
Существует большое количество математических моделей таких каналов. Простейшей из них является канал с независимой
Типичные последовательности и их свойства
Будем рассматривать последовательности статистически независимых букв. Согласно закону больших чисел, наиболее вероятными будут последовательности длиной n, в которых при количества N
Основная теорема Шеннона для дискретного канала с шумом
Формулировка
Для дискретного канала в шумом существует такой способ кодирования, при котором может быть обеспечена безошибочная передача все информации, поступающей от источ
Обсуждение основной теоремы Шеннона для канала с шумом
Теорема Шеннона для канала с шумом не указывает на конкретный способ кодирования, обеспечивающий достоверную передачу информации со скоростью, сколь угодно близкой с пропускной способности канала с
Пропускная способность непрерывного канала при наличии аддитивного шума
Рассмотрим следующую модель канала:
1. Канал способен пропускать колебания с частотами ниже Fm.
2. В канале действует помеха n(t), имеющая нормальный (гау
Шаг 2. Ввод текстовых файлов в Excel-таблицу с разбиением каждой строки текста на отдельные символы.
При вводе ранее сохраненного текстового файла следует указать тип файла *.*. Это позволит во время выбора видеть в списке все файлы. Укажите свой файл. После этого на экран будет выведено окно М
Шаг 4. Находим среднюю энтропию, приходящуюся на 1 букву сообщения.
Как описано в теоретическом введении, средняя энтропия находится по формулам 1 и 2. В обоих случаях нужно найти вероятности появления букв или двухбуквенных комбинаций..
Вероятности можно
Шаг 8. Напишем отчет о выполненной работе с описанием всех вычислений и о том, как они выполнялись. Прокомментируйте результаты.
Результаты вычислений представьте в виде таблицы:
<Язык 1>
<Язык
Подключение возможности использования нестандартных функций.
Программное управление приложениями, входящими в состав Microsoft Office, осуществляется при помощи так называемых макросов.
Слово Макрос – греческого происхождения. В перево
Создание нестандартной функции
Перед созданием нестандартных функций нужно открыть файл в рабочей книгой, содержащей информацию, которую нужно обработать с применением этих нестандартных функций. Если ранее эта рабочая книга был
Запись голоса и подготовка сигнала.
Запись начинается и заканчивается нажатием кнопки Record (рис. 5), помеченной красный кружком. В процессе записи кнопка Recоrd выглядит вдавленной и более светлой (подсвеченной).
Импорт текстовых данных в Excel
Двойным кликом откройте текстовый файл с экспортированные из программы Wavosaur данными (рис. 23).
Рис. 23. Примерный вид данных
Видно, что экспортированные
Квантование по уровню сводится к замене значения исходного сигнала уровнем того шага, в пределы которого это значение попадает.
Квантование по уровню – необходимое условие преобразования непрерывного сигнала в цифровую форму. Однако одного лишь квантования по уровню для этого недостаточно – для преобразования в цифровую фор
Коды Хаффмена
На этом алгоритме построена процедура построения оптимального кода, предложенная в 1952 году доктором Массачусетского технологического института (США) Дэвидэм Хаффменом[17]:
5) буквы перви
Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.
Рассмотрим алфавит из восьми букв. Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется три символа.
Наибольший эффек
Параметры эффективности оптимальных кодов
Таких параметров 2: коэффициент статистического сжатия и коэффициент относительной эффективности. Оба параметра характеризуют степень уменьшения средней длины кодового слова. При этом средняя длина
Особенности эффективных кодов.
5. Букве первичного алфавита с наименьшей вероятностью появления ставится в соответствие код с наибольшей длиной (лемма 1), т.е. такой код является неравномерным (с разной длиной кодовых слов). В р
Выполнение работы
Лабораторная работа №4 выполняется под управлением специально написанной управляющей программы. Эта управляющая программа написана на языке Visual Basic 6. Исполняемый файл программы носит и
Построение образующей матрицы
Линейные коды обладают следующим свойством: из всего множества 2k разрешенных кодовых слов можно выделить подмножества из k слов, обладающих свойством линейной независимост
Порядок кодирования
Кодовое слово КС получается путем умножения матрицы информационной последовательности ||X|| на образующую матрицу ||OM||:
||KC1*n|| = ||X
Порядок декодирования
В результате передачи кодового слова через канал оно может быть искажено помехой. Это приведет к тому, что принятое кодовое слово ||ПКС|| может не совпасть с исходным ||КС||.
Выполнение работы
Лабораторная работа №5, как и работа №4, выполняется под управлением управляющей программы, написанной на алгоритмическом языке Visual Basic 6. Исполняемый файл программы носит имя Помехо
Новости и инфо для студентов