ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ

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

2015-01-30

87.16 KB

5 чел.


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск



Баранов Виктор Павлович.
Дискретная математика. Раздел 3. Графы, сети, коды.

Лекция 17-18. Введение в теорию кодирования

Лекция 17-18. ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ

План лекции:

1. Предисловие.

2. Самокорректирующиеся коды.

3. Основные характеристики кода. Алгоритмы декодирования.

4. Линейные коды.

  1.  Предисловие

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

  1.  Самокорректирующиеся коды

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

Если уровень помех в канале высокий, то передача данных без каких-либо средств борьбы с помехами становится в принципе невозможной.

Основным средством борьбы с ошибками при передаче по каналу связи является введение избыточности, при этом происходит снижение скорости передачи.

В общем случае процесс передачи информации с введением избыточности можно представить в виде следующей схемы.

1°. Передаваемая информация – длинная последовательность нулей и единиц – разбивается на блоки по  символов.

2°. Каждый блок кодируется двоичным словом из  символов, где .

3°. Коды передаются по каналу связи и принимаются на другом его конце с возможными искажениями.

4°. Искаженные коды подвергаются процедуре декодирования, в результате которой восстанавливается первоначальный блок из  символов.

Первым примером такой схемы передачи информации был 7-разрядный код Хемминга, исправляющий единичные ошибки.

Передаваемая информация разбивается на блоки по 4 символа (полубайты), блоки кодируются словами из 7 символов: .

Разряды кодового слова определяются так. Полубайт записывается в разряды 3, 5, 6, 7 (информационные): .

Остальные разряды кодового слова (контрольные) определяют так, чтобы выполнялись соотношения:

,

,

.

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

,

,

.

Если ошибок не было, все три суммы равны нулю. Если был искажен один разряд, то  – его номер.

  1.  Основные характеристики кода. Алгоритмы декодирования

Кодом длины  называется любое подмножество двоичных слов длины :

.

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

Чтобы описать действие помех при передаче и процедуру декодирования, на множестве двоичных слов вводится метрика. Расстоянием между двоичными словами называется количество разрядов, в которых эти слова различаются:

, , .

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

1°. , .

2°. .

3°. .

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

Если передавалось слово , а принято слово , то  равно количеству разрядов, искаженных при передаче (число ошибок).

Будем предполагать, что вероятность искажения символа при передаче невелика (в противном случае таким каналом связи нельзя пользоваться). Основываясь на некоторой вероятностной модели можно строго доказать, что наилучшим алгоритмом декодирования при сделанных предположениях будет следующий:

если принято слово , то считаем, что передавалось слово , ближайшее к слову .

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

В дальнейшем будем считать, что на приемном конце канала используется именно этот алгоритм декодирования.

Рассмотрим главные параметры, характеризующие код.

1°. Мощность кода , то есть количество кодовых точек. Если код имеет мощность , то блоки информации, которые он кодирует должны иметь длину , такую, что , то есть . Примем физическую скорость передачи канала за единицу: передача одного двоичного символа занимает одну единицу времени. Применив кодирование, получим, что  двоичных символов передаются за  единиц времени, то есть скорость передачи информации равна

бит/ед. вр.

Следовательно, чем больше мощность кода, тем большую скорость передачи информации он обеспечивает.

2°. Кодовое расстояние – минимальное расстояние между кодовыми словами:

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

Теорема 1. Если , то код  исправляет  ошибок.

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

Очевидно, что  и будет ближайшим к  кодовым словом, так как для любого другого кодового слова  имеем

Теорема доказана.

Основной задачей теории кодирования является следующая:

Для заданных  построить код  максимальной мощности такой, что .

  1.  Линейные коды

Совокупность  двоичных слов длины  вместе с операцией поразрядного сложения по модулю 2 образует -мерное векторное пространство над полем .

Код  называется линейным, если он является подпространством этого пространства.

Рассмотрим способы задания линейного кода. Первый способ состоит в задании базиса  из  векторов подпространства размерности . Тогда

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

Если эти уравнения независимы, то размерность пространства решений равна . Бинарная матрица системы  имеет размер . Тогда

.                                                            (1)

Матрица  называется проверочной матрицей кода .

Пример. Описанный выше 7-разрядный код Хемминга представляет собой линейный код с проверочной матрицей

.

Так как

,

то из условия , получаем соотношения, которым удовлетворяют разряды кодовых слов в коде Хэмминга

Эти соотношения представляют собой проверки на четность. Например, первое из них выполняется, когда количество единиц в разрядах 4, 5, 6 и 7.

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

.

Теорема 2. Если  – линейный код, то

,

то есть минимум берется по всем ненулевым словам кода.

Это утверждение очевидным образом следует из следующих двух фактов

Теорема 3. Линейный код исправляет  ошибок, если в его проверочной матрице  любые  столбцов линейно независимы.

Доказательство. Обозначим столбцы проверочной матрицы . Условие  для ненулевого слова , принадлежащего коду, можно записать в виде

.                                                           (2)

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

1



 

Другие похожие работы, которые могут вас заинтересовать.
9039. Введение в теорию множеств 376.48 KB
  В качестве примера можно привести числовые системы: множество натуральных чисел – дискретный объект а множество действительных чисел – непрерывный. Обычно множество объясняют следуя основателю теории множеств Г. Объекты составляющие множество называют его элементами. Если каждый элемент множества входит в множество то называется подмножеством .
10788. Введение в экономическую теорию 18.97 KB
  Предмет экономической теории и основные экономические понятия: экономические блага потребности ресурсы экономический выбор экономические отношения объекты микроэкономики.Экономическая политика и методы экономической теории. Структура экономической науки.Основные этапы развития экономической теории.
7485. Введение в теорию роста. Модель Солоу 456.46 KB
  Введение в теорию роста. Введение в неоклассическую теорию экономического роста: технический анализ. Траектория сбалансированного роста. Воздействие изменения нормы сбережений на капитал выпуск и потребление на траектории сбалансированного роста.
7453. Введение в экономическую теорию и общественное производство 29.83 KB
  Сущность и элементы общественного производства. Экономика это наука о способах использования ограниченных ресурсов общества для производства товаров и услуг и их распределения среди различных групп людей. Можно выделить три уровня производства: процесс труда отдельного индивидуума производство в рамках предприятия микроуровень производство в рамках общества государства страны макроуровень производство в рамках мира Элементы общественного производства: рабочая сила это совокупность определенных физических и духовных...
14330. Элементы теории кодирования 50.74 KB
  Кодирование информации процесс преобразования сигнала из формы удобной для непосредственного использования информации в форму удобную для передачи хранения или автоматической переработки Объектом кодирования служит как дискретная так и непрерывная информация которая поступает к потребителю через источник информации. В теории кодирования существует ряд направлений...
4464. Основные понятия и методы теории информатики и кодирования 31.67 KB
  Сигналы, данные, информация; информация как предмет изучения информатики; свойства информации; классификация информации. Понятие экономической информации, ее свойства. Структура экономической информации. Классификация экономической информации.
2003. Введение в VPL 531.3 KB
  Введение в VPL Microsoft Visul Progrmming Lnguge VPL является средой разработки приложений основанной на графической модели программирования. Благодаря этому VPL хорошо подходит для программирования различных параллельных или распределённых сценариев. VPL рассчитана на начинающих программистов понимающих такие основы как переменные и логика. Однако VPL предназначена не только для новичков.
6259. Введение в БЖД 12.46 KB
  Основные направления государственной политики в области охраны труда. Государственный надзор и контроль за охраной труда. В соответствии с принятой физиологической классификацией трудовой деятельности различают следующие формы труда. Формы труда требующие значительной мышечной энергии.
6604. ВВЕДЕНИЕ В ООП 24.63 KB
  Абстрактных типов данных определенных пользователем; определение всех необходимых операций для каждого класса; обеспечение расширяемости открытости классов с использованием принципа наследования...
7462. Введение в макроэкономику 85.24 KB
  Основные макроэкономические показатели: 1 Валовой продукт ВНП ВВП; 2 Чистый национальный продукт чистый внутренний продукт; 3 Национальный доход; 4 Личный доход; 5 Располагаемый доход. Валовой национальный продукт ВНП – это валовой продукт произведенный гражданами страны с помощью факторов производства принадлежащих данной стране неважно – на территории данной страны или за ее пределами. Если же предприятие носит совместный характер то для подсчета ВВП и ВНП приходится вычленять вклад в создание его продукции различных факторов...
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.