АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Цель работы

Читайте также:
  1. I. Организация выполнения выпускной квалификационной работы
  2. II. ПЕРЕЧЕНЬ ЗАДАНИЙ ДЛЯ ВЫПОЛНЕНИЯ РАБОТЫ
  3. II. Порядок подготовки, защиты и оценки квалификационной работы
  4. II. Работы учеников Уильяма Джеймса: Дж. Дьюи, С. Холла, Дж. Кэттела, Э. Торндайка
  5. II. Рекомендации по оформлению контрольной работы.
  6. II. Требования охраны труда перед началом работы.
  7. II. Требования охраны труда перед началом работы.
  8. II. Требования охраны труда перед началом работы.
  9. III. Задания для самостоятельной работы по изучаемой теме
  10. III. Задания для самостоятельной работы по изучаемой теме
  11. III. Задания для самостоятельной работы по изучаемой теме
  12. III. Задания для самостоятельной работы по изучаемой теме

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

 

Введение

 

Методические указания адресованы студентам очной и заочной форм обучения направления подготовки 0915 - «Компьютерная инженерия», изучающим дисциплину «Теория информации и кодирование».

Необходимыми условиями успешного изучения данной дисциплины являются хорошие знания по курсам «Высшая математика», «Дискретная математика», «Прикладная теория цифровых автоматов» и «Теория вероятностей и математическая статистика».

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

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

 

1. Основные понятия и определения

 

С некоторыми основными понятиями и определениями по разделу «Кодирование информации» студенты ознакомлены ранее при изучении раздела «Эффективные коды» [9].

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

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

Существуют блоковые и непрерывные корректирующие коды. Блоковые коды бывают разделимыми и неразделимыми. В разделимых кодах чётко различаются информационные и проверочные символы. В неразделимых кодах это сделать невозможно. Наиболее многочисленный класс разделимых кодов составляют линейные коды. В разделимых линейных кодах контрольные символы образуются как линейные комбинации информационных символов.

Например, пусть некоторый символ первичного алфавита представлен безызбыточным кодовым словом а1а2…аn, где то есть все n разрядов являются информационными. Чтобы построить кодовое слово с проверкой на чётность, надо определить значение дополнительного проверочного разряда «c» по формуле

где - линейная операция сложения по модулю 2. Построенный таким образом код длиной (n+1) обнаруживает все одиночные ошибки. Правильно переданное кодовое слово такого кода содержит четное число единиц. Количество единиц в кодовом слове называется его весом.

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

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

 

2. Блоковые коды

2.1. Общие принципы введения избыточности

 

Здесь и далее рассматриваются только двоичные коды.

На вход кодера канала поступает последовательность из k информационных символов (k-разрядное двоичное слово). На выходе кодера получается n двоичных символов (n-разрядное двоичное слово), при этом n>k. Всего можно сформировать 2k входных последовательностей и 2n - выходных последовательностей. Входные последовательности числом 2k называются разрешёнными, остальные (2n-2k) последовательностей – запрещёнными последовательностями.

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

- 2k случаев безошибочной передачи (разрешенные комбинации);

- 2k (2k-1) случаев перехода в другие разрешённые комбинации (необнаруживаемые ошибки);

- 2k(2n-2k) случаев перехода в неразрешённые комбинации (обнаруживаемые ошибки).

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

 

2.2. Исправление ошибок

 

Основная идея: всё множество 2n комбинаций разбивается на 2k непересекающихся подмножеств, количество случаев перехода в неразрешённые кодовые комбинации 2k(2n-2k). Каждое подмножество содержит (2n-2k)/2k запрещённых кодовых комбинаций. Если передаваемая комбинация трансформировалась в «своё» подмножество, то ошибка будет исправлена. Всего таких случаев насчитывается

Взаимно независимые ошибки задаются вероятностью р неверной передачи двоичного сигнала. Количество искажённых сигналов R называется кратностью ошибки. Значение вероятности появления ошибки кратности R вычисляется по формуле

При р<<1 наиболее вероятны ошибки низкой кратности.

 

2.3. Связь корректирующей способности кода с кодовым расстоянием

 

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

Cod 1   Кодовое расстояние
Cod 2  
      d12=6

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

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

(1). Невозможность обнаружения ошибок. Пусть задан код из четырех двухразрядных двоичных кодовых слов (n=2):

Cod 1=00; Cod 2=01; Cod 3=10, Cod 4=11.

Несложно подсчитать, что минимальное кодовое расстояние dmin=1. Любая одиночная ошибка трансформирует конкретную кодовую комбинацию в другую разрешенную кодовую комбинацию, то есть все возможные кодовые комбинации разрешены, избыточности нет, поэтому код не обладает корректирующей способностью.

(2). Обнаружение одиночной ошибки. Пусть код содержит четыре трехразрядных двоичных кодовых слова (n=3):

Cod 1=000; Cod 2=110; Cod 3=101; Cod 4=011.

Минимальное кодовое расстояние dmin=2. При одиночной ошибке ни одна из разрешенных кодовых комбинаций с четным весом не переходит в другую разрешенную кодовую комбинацию. Данный код позволяет обнаруживать одиночные ошибки. Одиночная ошибка в каждой из разрешенных кодовых комбинаций приводит к появлению одного из запрещенных кодовых слов с нечетным весом:

100, 010, 001, 111.

Исправить такую ошибку невозможно.

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

(2.1)

(3). Исправление одиночной ошибки. Пусть код включает два разрешенных кодовых слова: 000 и 111 с хэмминговым расстоянием d=3.

Подмножество последовательностей, в которые может трансформироваться некоторая разрешённая комбинация, не должно пересекаться с другими подмножествами: разрешенному кодовому слову 000 приписывается подмножество {100, 010, 001}, а разрешенному кодовому слову 111 - подмножество {011, 101, 110}, что соответствует одиночной ошибке при передаче разрешенного кодового слова. Декодирование осуществляется таким образом, чтобы любая запрещенная кодовая комбинация отождествлялась с наиболее «близкой» (по Хэммингу) разрешенной кодовой комбинацией (декодирование по методу максимального правдоподобия).

Для исправления одной ошибки необходимо dmin≥3.

Если требуется исправить ошибки кратности S, необходимо, чтобы выполнялось неравенство

(2.2)

Для обнаружения всех ошибок кратности R и одновременного исправления ошибок кратности S минимальное хэммингово расстояние нужно выбирать из условия

(2.3)

при этом

R>S. (2.4)

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)