Принципы помехоустойчивого кодирования реферат

Обновлено: 16.05.2024

Теория кодирования возникла в конце 40-х годов с появлением работ Голея, Хэмминга и Шеннона. Истоками теории являются инженерные задачи, но ее развитие приводит к все более утонченным математическим методам. Первые два автора заложили основу алгебраическим методам кодирования, Шеннон предложил и исследовал понятие случайного кодирования.

Содержание работы

1. ВВЕДЕНИЕ 4
2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 5
3. ПРАКТИЧЕСКАЯ ЧАСТЬ 10
4. ЗАКЛЮЧЕНИЕ 13
5. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 14

Файлы: 1 файл

Казанский Государственный Технический Университет им (2).docx

Казанский Государственный Технический Университет им. А.Н. Туполева

Институт радиоэлектроники и телекоммуникаций

Кафедра Радиоэлектронных и Телекоммуникационных систем

______________________________ ______________________________ ______

Пояснительная записка к курсовой работе по курсу

ТЕОРИЯ ЭЛЕКТРИЧЕСКОЙ СВЯЗИ

Выполнил:
Студент группы 4404
Супрунов Д.О.

Проверил:
Доцент кафедры РТС
Коробков А.А.

Задание

2. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 5

3. ПРАКТИЧЕСКАЯ ЧАСТЬ 10

4. ЗАКЛЮЧЕНИЕ 13

5. СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 14

ВВЕДЕНИЕ

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

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Клодом Шенноном. Он сформулировал теорему для дискретного канала с шумом: при любой скорости передачи двоичных символов, меньшей, чем пропускная способность канала, существует такой код, при котором вероятность ошибочного декодирования будет сколь угодно мала.

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

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

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

Обнаружить ошибку [2] - зафиксировать факт, что в данной кодовой комбинации присутствует ошибка.

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	реферат
Язык	русский
Дата добавления	10.03.2017
Размер файла	160,4 K

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

Основы помехоустойчивого кодирования

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

Растущая потребность в точной передаче информации

Рассмотреть и проанализировать принцип работы помехоустойчивых кодов

Принципы помехоустойчивого кодирования

· обработка и анализ научных источников

· поиск информации по выбранной теме в Интернет источниках

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

Классификация помех и их источников:

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

2. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

В основном принцип помехоустойчивых кодов строится на прибавлении к исходной комбинации (kсимволов) контрольных (rсимволов). Закодированная комбинация будет содержать nсимволов. Коды с таким преобразованием часто называют (n,k) коды.

Где k--число символов в исходной комбинации,

r--число контрольных символов.

2.1.1 Коды с обнаружением ошибок

2.1.1.1 Код с проверкой на четность

Этот код образуется путем прибавления к передаваемому коду, состоящему из k символов, одного контрольного символа (0 или 1), так, чтобы общее число единиц в передаваемом коде было четным.

Определим, каковы обнаруживающие свойства этой комбинации. Вероятность Poo обнаружения ошибок находится по формуле

В связи с тем, что вероятность ошибок является очень малой величиной, то можно сократить формулу

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

При передаче большого количества кодовых комбинаций Nk , число комбинаций, в которых ошибка определяется, равно:

Общее число кодовых комбинаций с обнаруживаемыми и не обнаруживаемыми ошибками находится как

Тогда коэффициент обнаружения Kобн для комбинаций с четной защитой равен

2.1.1.2 Код с постоянным весом

Такой код содержит неизменное число единиц и нулей. Число кодовых комбинаций составит

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

Для примера возьмём код с тремя единицами из семи. Для такого кода возможны три варианта смещений.

Вероятность возникновения не обнаруживаемых ошибок смещения

Если ошибка произойдет в старшем разряде, то это приведет к максимальной ошибке, на 3600. А код Грея, это такой код в котором все соседние комбинации отличаются только одним символом, поэтому при переходе от изображения одного числа к изображению соседнего происходит изменение только на единицу младшего разряда. Ошибка будет минимальной.

Схема съема информации угла поворота вала в код

Код Грея записывается следующим образом

Разряды в коде Грея не имеют постоянного веса. Вес kразряда определяется следующим образом

При этом все нечетные единицы, считая слева направо, имеют положительный вес, а все четные единицы отрицательный.

2.1.2 Корректирующие коды

Корректирующие коды - это коды, которые позволяют обнаруживать и исправлять ошибки. Принцип представления корректирующих кодов можно представить по средствам N-мерного куба. Возьмем трехмерный куб (рисунок ниже), с длиной ребер равной единице. Вершины куба отображают двоичные коды. Минимальное расстояние между вершинами определяется минимальным количеством ребер, которые находятся между вершинами. Такое расстояние называется кодовым (или хэмминговым) и обозначается буквой d.

Рис.5.3. Представление двоичных кодов с помощью куба

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

определим, что расстояние между ними d=7.

Для кода с N=3 восемь кодовых комбинаций размещаются на вершинах трехмерного куба. Такой код имеет кодовое расстояние d=1, и для передачи используются все восемь кодовых комбинаций 000,001. 111. Такой код является не помехоустойчивым, он не в состоянии обнаружить ошибку.

Если выберем комбинации с кодовым расстоянием d=2, например, 000,110,101,011, то такой код позволит обнаруживать однократные ошибки. Назовем эти комбинации разрешенными, предназначенными для передачи информации. Все остальные 001,010,100,111 - запрещенные.

Любая одиночная ошибка приводит к тому, что разрешенная комбинация переходит в ближайшую, запрещенную комбинацию (см. рис.5.3). Получив запрещенную комбинацию, мы обнаружим ошибку. Выберем далее вершины с кодовым расстоянием d=3

Большинство корректирующих кодов представляют собой линейные коды. Линейные коды - это коды, в которых контрольные символы образуются линейным комбинированием информационных символов. Также корректирующие коды являются групповыми кодами. Групповые коды (Gn) - это коды, имеющие одну основную операцию. При том, должно соблюдаться условие замкнутости (то есть, при сложении двух элементов группы получается элемент принадлежащий этой же группе ). Число разрядов в группе не должно увеличиваться. Этому условию удовлетворяет операция поразрядного сложения по модулю 2. В группе, кроме того, должен быть нулевой элемент.

Большая часть корректирующих кодов строятся на добавлении к исходной k комбинации r контрольных символов. По итогу в линию передаются n=k+r символов. Тогда корректирующие коды называются (n,k) кодами. Как определить необходимое количество контрольных символов?

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

помеха код начальный ошибка

Это равнозначно известной задаче о минимуме числа контрольных вопросов, на которые можно дать ответы вида “да” или “нет”, для однозначного определения одного из элементов конечного множества.

Эта формула называется неравенством Хэмминга, или нижней границей Хэмминга для числа контрольных символов.

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

1. Вернер М. Основы кодирования. -- М.: Техносфера, 2004.

2. Зюко А.Г., Кловский Д.Д., Назаров М.В., Финк Л.М. Теория передачи сигналов. М: Радио и связь, 2001 г. -368 с.

3. Кнут Дональд, Грэхем Роналд, Паташник Орен Конкретная математика. Основание информатики -- М.: Мир; Бином. Лаборатория знаний, 2006. -- С. 703.

5. Метрология и радиоизмерения в телекоммуникационных системах. Учебник для ВУЗов. / В.И.Нефедов, В.И. Халкин, Е.В. Федоров и др. - М.: Высшая школа, 2001 г. - 383с.

6. Рудаков А.Н. Числа Фибоначчи и простота числа 2127-1 // Математическое Просвещение, третья серия. -- 2000. -- Т. 4.

7. Стахов А.П. Коды золотой пропорции. -М.: Радио и Связь, 1984.

8. Цапенко М.П. Измерительные информационные системы. - М.: Энергоатом издат, 2005. - 440с.

Подобные документы

Сущность метода перестановочного декодирования. Особенности использования метода вылавливания ошибок. Декодирование циклического кода путем вылавливания ошибок. Распознавание пакетов ошибок как особенность циклических кодов. Вычисление вектора ошибок.

доклад [20,3 K], добавлен 24.05.2012

Коды Боуза-Чоудхури-Хоквингема (БЧХ) – класс циклических кодов, исправляющих многократные ошибки. Отличие методики построения кодов БЧХ от обычных циклических. Конкретные примеры процедуры кодирования, декодирования, обнаружения и исправления ошибок.

реферат [158,2 K], добавлен 16.07.2009

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

доклад [12,6 K], добавлен 11.11.2010

Использование принципа формирования кода Хэмминга в процессе отладки ошибки. Сложение двоичного числа по модулю в программе и получение кода ошибки для определения разряда, в котором она содержится. Соответствие ошибки определенному разряду операнда.

лабораторная работа [8,0 K], добавлен 29.06.2011

Фаза "избавления" программы от ошибок. Задача обработки ошибок в коде программы. Ошибки с невозможностью автоматического восстановления, оператор отключения. Прекращение выполнения программы. Возврат недопустимого значения. Директивы РНР контроля ошибок.

учебное пособие [62,3 K], добавлен 27.04.2009

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

курсовая работа [428,4 K], добавлен 29.04.2015

Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона.

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

Содержание

ВВЕДЕНИЕ…………………………………………………………………………………………..3
ГЛАВА 1. Общие сведения о помехоустойчивом кодировании.………………………………. 4
1.1. Помехоустойчивость…………………………………………………………………………. 5
1.2. Основные принципы помехоустойчивого кодирования…………………………………….5
1.3. Основные параметры помехоустойчивых кодов……………………………………………..9
ВЫВОДЫ ПО 1 ГЛАВЕ……………………………………………………………………………11
ГЛАВА 2. Коды помехоустойчивого кодирования информации……………………………….12
2.1. Краткая классификация помехоустойчивых кодов………………………………………….12
2.2. Основные помехоустойчивые коды…………………………………………………………..15
2.3. Особенности практического кодирования…………………………………………………. 23
ВЫВОДЫ ПО 2 ГЛАВЕ……………………………………………………………………………28
ЗАКЛЮЧЕНИЕ……………………………………………………………………………………..29
ЛИТЕРАТУРА………………………………………………………………………………………30

Прикрепленные файлы: 1 файл

Помехоустойчивое кодирование информации (1).doc

ГЛАВА 1. Общие сведения о помехоустойчивом кодировании.………………………………. 4

1.2. Основные принципы помехоустойчивого кодирования…………………………………….5

1.3. Основные параметры помехоустойчивых кодов…………………… ………………………..9

ГЛАВА 2. Коды помехоустойчивого кодирования информации……………………………….12

2.1. Краткая классификация помехоустойчивых кодов………………………………………….12

2.2. Основные помехоустойчивые коды…………………………………………………………..15

2.3. Особенности практического кодирования………………………………………………… . 23

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

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

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

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

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

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

Объект: Кодирование информации.

Предмет: Помехоустойчивое кодирование информации.

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

ГЛАВА 1. Общие сведения о помехоустойчивом кодировании

Код принимаемого языка определяется алфавитом символов и правилами их комбинирования, т.е. правилами построения знаков различного ранга. Число символов в алфавите называется основанием кода. Знаки второго ранга называются кодовыми словами. Если все кодовые слова имеют одинаковое число символов, то код называется равномерным, в противном случае код называется неравномерным. Пример применения равномерного кода приведен в таблице 1.

Рис. 1. Колебания частот

Сигналы символов могут быть простыми и сложными.

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

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

1.2. Принципы помехоустойчивого кодирования

Вначале будет рассмотрен двоичный канал связи с помехами, приводящими к тому, что ошибки появляются независимо в каждом символе и средняя вероятность ошибки равна Р=0,01. Если требуется рассмотреть произвольный блок из 10 символов на выходе канала, то весьма трудно выявить символы, которые являются ошибочными. Вместе с тем, если считать, что такой блок содержит не более трех ошибок, то мы будем неправы лишь два раза на миллион блоков. Кроме того, вероятность, что мы окажемся правы, возрастает с увеличением длины блока. При увеличении длины блока доля ошибочных символов в блоке стремится к средней частоте ошибок в канале, а также, что очень важно, доля блоков, число ошибок в которых существенно отличается от этого среднего значения, становится очень малой. Простые вычисления помогают понять, насколько верным является это утверждение. Рассмотрев, например, тот же канал, можно вычислить вероятность того, что доля ошибочных символов превышает значение p, и построить график этой функции для нескольких значений длины блока.

Рис. 2. Вероятность того, что доля ошибочных символов e/N в блоке длиной N превышает р при вероятности Р _e=0,01

Название работы: ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ И ПЕРЕМЕЖЕНИЕ. ПРИНЦИПЫ ПОМЕХОУСТОЙЧИВОГО КОДИРОВАНИЯ

Предметная область: Информатика, кибернетика и программирование

Размер файла: 632.57 KB

Работу скачали: 66 чел.

ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ И ПЕРЕМЕЖЕНИЕ

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

путем соответствующим образом подобранных проверочных символов.

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

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

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

В декодере осуществляется обратная операция: по принятой последовательности символов определяется наиболее вероятное переданное кодовое слово. Если все переданные кодовые слова равновероятны, а канал связи не имеет памяти, то в качестве наиболее вероятного переданного слова при жестких решениях в демодуляторе выбирается то, которое ближе всех в смысле расстояния Хэмминга находится к принятому кодовому слову. Расстояние Хэмминга между последовательностями Y и Z оценивается как вес (число двоичных единиц) слова, образованного посимвольным сложением по модулю 2 последовательностей Y и Z. ( Y =101011, Z =011001, Z + Y =110010, расстояние= 3)

Если обозначить вероятность ошибки при приеме символов в системах без кодирования и с блоковым кодированием соответственно p 0 , и p 1 , то вероятности ошибочного приема в системе без кодирования и с кодированием будут определяться соответственно выражениями:

количество возможных конфигураций из n символов , содержащих i ошибок

k - длина блока без кодирования

n - длина кодированного блока

r = n - k число проверочных символов

t - кратность исправляемых ошибок

Здесь предполагается, что код имеет минимальное Хэммингов расстояние d min и исправляет все ошибки кратности

Между параметрами n , k и t блокового кода существует определенное соотношение, устанавливаемое так называемой границей Хэмминга

Коды, для которых соотношение (3.3) выполняется строго, называются совершенными. Примером совершенных кодов служит код Хэмминга, исправляющий одиночные ошибки, и код Голея. Другие коды могут исправлять некоторые конфигурации ошибок, кратность которых превышает t . Для этих кодов (3.3) следует трактовать как полезную верхнюю границу.

В табл.3.1 приведены примеры блоковых кодов, исправляющих ошибки кратности t. и их параметры.

В классе циклических кодов наиболее важен подкласс так называемых кодов БЧХ. Эти коды могут быть построены для широких диапазонов длины блока, кодовой скорости и исправляющей способности. В частности, если t кратность исправляемых ошибок в пределах блока, m произвольное целое число, то длина кодового слова, количество проверочных символов и кодовое расстояние удовлетворяют соотношениям:

В табл.3.2 в качестве примера приведены соотношения между;: . параметрами некоторых кодов БЧХ. Отметим, что при t=1 параметры n и k соответствуют параметрам кода Хэмминга. Иначе говоря, код Хэмминга также является кодом БЧХ, исправляющим одиночные ошибки.

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

Сверточные (или рекуррентные) коды отличаются от блоковых кодов структурой. В блоковом коде n символов кода, формируемых кодером любой выбранный интервал времени, зависят только от k информационных символов, поступивших на его вход в течение этого же интервала времени. В сверточном коде блок из n символа кода, формируемых кодером в любой выбранный интервал времени, зависит не только от k информационных символов, поступивших на его вход в течение этого же интервала времени, но и от информационных символов, поступивших в течение (К 1) предыдущих интервалов. Параметр К называется длиной кодового ограничении. Для сверточных кодов значение параметров n и k выбираются .малыми. Сверточные коды могут использоваться для исправления случайных ошибок, ошибок, группирующихся в пакеты, и для тех и, других. Кодер двоичного сверточного кода содержит kK-разрядный регистр и n сумматоров по mod2. Обобщенная структурная схема кодера сверточного кода приведена на рис.3.3.

На рис.3.4 приведены пример кодера сверточного кода с параметрами k=1, n=2, К=З, 1/2. Информационные символы поступают на вход регистра, а символы кода формируются на выходе коммутатора. Коммутатор (КМ) последовательно опрашивает выходы сумматоров по mod 2 в течение интервала времени, равного длительности информационного символа (бита).

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

имеет порождающие векторы g 1=111 и g 2 =1О1 и порождающие многочлены g 1(х)=х 2 +х+1: и g 2(х)=х 2 +1. Кроме того, сверточный код может быть задан импульсной характеристикой, определяемой как последовательность символов кода на выходе кодера при подаче на его вход единственного символа 1. Легко проверить; что импульсная характеристика данного кода равна 111011. Так операция сложения появляется линейной операцией, сверточные коды относятся к классу линейных и выходная последовательность кодера может рассматриваться как результат свертки входной последовательности с импульсной характеристикой кодера. Отсюда и происходит название коды и метода кодирования.

Процедуры кодирования и декодирования удобно описывать с помощью так называемого кодового дерева, которое отображает последовательности на выходе кодера для любой. возможной входной последовательности. На рис.3.5 приведено кодовое дерево кодера, изображенного на рис.3.4, для блока из. пяти информационных символов. Если первый, символ принимает значение 0, то на выходе кодера формируется пара символов 00. Если первый символ принимает значение 1, то на выходе кодера формируется пара символов 11. Это показано с помощью двух ветвей, которые выходят из начального узла. Верхняя ветвь соответствует 0, нижняя 1. В каждом из последующих узлов ветвление происходит аналогичным образом: из каждого узла исходит две ветви, причем верхняя ветвь соответствует 0, а нижняя -1. Ветвление будет происходить вплоть до последнего символа входного блока. Вслед за ним все входные символы принимают значение 0, и образуется только одна обрывающаяся ветвь. Таким образом, каждой из возможных входных комбинаций информационных символов соответствует своя вершина на кодовом дереве. В данном случае имеется 32 вершины. С помощью кодового дерева легко построить выходную последовательность символов кода, соответствующую определенной входной последовательности. Например, входной последовательности 11010 соответствует выходная последовательность, лежащая на пути, изображенном пунктирной линией. Анализируя

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

Обозначим четыре узла третьего уровня, т.е. узлы, в которых происходит третье ветвление, буквами а, b, с, d. Повторяющаяся структура ветвей имеет место и для узлов четвертого и пятого уровней, поэтому их также можно обозначить этими же буквами. Для узлов пятого уровня любой из четырех комбинаций (11,10,01, 00) первых двух входных символов будет соответствовать один и тот же выходной символ.

Таким образом, поведение кодера можно полностью описать с помощью диаграммы состояний, изображенной на рис.3.6,а или направленного графа с четырьмя состояниями (рис.3.6,б) который устанавливает однозначное соответствие между входными и выходными символами кодера. На графе сплошные линии соответствуют входному символу 0, а пунктирные символу 1. Например, если кодер находится в состоянии а и на вход поступает 1, то на выходе декодера будет формироваться комбинация 11 (пунктирная линия) и декодер перейдет в состояние , соответствующее R,=0 и R,=1. Аналогичным образом при поступлении 0 декодер останется в состоянии а (сплошная линия) и на выходе будет формироваться комбинация 00.

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

Другим полезным способом описания кодового дерева является решетчатая диаграмма, изображенная на рис.3.7. Диаграмма берет начало из состояния а и на ней отображаются все возможные переходы при поступлении на вход очередного символа. Сплошным линиям соответствуют переходы, происходящие при поступлении символа 1 пунктирным символа 0. При поступлении на вход двух символов кодер оказывается в одном из четырех состояний: а, b , с или б. Заметим, что решетчатая диаграмма имеет повторяющийся характер и может быть легко построена с помощью диаграммы состояний.

3.8. МЕТОДЫ ПЕРЕМЕ Ж ЕНИЯ

Изменение по определенному правилу естественного порядка следования символов в некоторой кодовой последовательности называют процедуру перемещением (Interleaving), обратную перемежению, принято называть деперемеженаем (deinterleaving). В результате выполнения процедуры деперемежения восстанавливается естественный порядок следования символов.

Рассмотрим некоторые эффективные методы перемежения.

БЛОКОВОЕ ПЕРЕМЕ Ж ЕНИЕ

При блоковом перемежении кодовые слова длиной n символов записываются в виде таблицы шириной W и глубиной D символов, как показано на рис.3.14.

Предположим, что W=n. Тогда строки таблицы представляют собой кодовые слова, содержащие k информационных символов и (и - k) проверочных символов. После заполнения таблицы осуществляется последовательное считывание символов по столбцам и их передача по каналу связи. В приемнике выполняется обратная процедура последовательная запись символов по столбцам до полного заполнения таблицы. Затем производится считывание символов по строкам таблицы и их декодирование. Такой перемежитель позволяет разрушить пакет ошибок длиной , в результате чего в каждом кодовом слове будет не более одной ошибки.

Однако периодическая последовательность одиночных ошибок, отстоящих друг от друга на D символов, будет вызывать полное поражение ошибками некоторого одного слова. Задержка при выполнении процедур перемежения- деперемежения равна 2WD сим волов. Объем памяти и перемежителя и деперемежителя составляет WD символов.

Другой возможный вариант выполнения перемежителя изображен на рис.3.15. Здесь

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

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

При межблоковом перемежении в качестве входного блока принимается блок из NB символов, и каждый блок из N символов распределяется между следующими В выходными блоками. Пусть х и у представляют собой соответственно входной и выходной символы перемежителя. Тогда правило отображения символа i-го входного блока в символ выходного блока можно определить следующим образом:

Пример межблокового перемежения при В=З и И=2 показан на рис.3.16. Здесь символы i-ro, (i+1)-го и (i+2)-го входных кодовых блоков обозначены соответственно а,b,с. Согласно приведенному правилу отображения

СВЕРТОЧНОЕ ПЕРЕМЕ Ж ЕНИЕ

Структурная схема сверточного перемежителя-деперемежителя приведена на рис.3.17. Предполагается, что имеется синхронизация мультиплексоров и демультиплексоров передатчика и приемника.

Демультиплексор осуществляет последовательное подключение выхода кодера к различным строкам памяти перемежителя. Мультиплексор соответственно подключает вход декодера к различным строкам памяти деперемежителя. Каждая строка памяти представляет собой регистр сдвига, количество элементов задержки которого указано соответствующим числом, вписанным в прямоугольник. Первый элемент кодированной последовательности записывается в верхнюю строку и сразу же передается по каналу связи. Записывается он также в первую строку памяти деперемежителя, обеспечивающей задержку на (В 1)М символов. Второй элемент кодированной последовательности записывается во вторую строку памяти перемежителя, обеспечивающей задержку на М символов. Таким образом, смежные символы кодированной последовательности оказываются разнесенными на М символов. Поэтому на них не оказывают влияние пакеты ошибок, длина которых не превышает М. При приеме второй символ дополнительно задерживается на (В 2)М символов, так что общая задержка символов составляет (В 1)М символов. Следует отметить, что все символы кодовой последовательности после перемежения и деперемежения имеют одинаковую задержку, поэтому порядок следования символов на выходе кодера и входе декодера сохраняется одним и тем же.

Лекция 5. Принципы помехоустойчивого кодирования ( реферат , курсовая , диплом , контрольная )

Ошибка в кодовой комбинации появляется при ее передаче по каналу связи вследствие замены одних элементов другими под воздействием помех. Например, 2-кратная ошибка возникает при замене (искажении) двух элементов: если кодовая комбинация 110 111 принята как 100 110, то имеет место двукратная ошибка.

Теория помехоустойчивого кодирования базируется на результатах исследований, проведенных Шенноном и сформулированных в виде теоремы:

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

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

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

Обеспечение передачи информации с весьма малой вероятностью ошибки и достаточно высокой эффективностью возможно при кодировании чрезвычайно длинными последовательностями знаков.

На практике точность передачи информации и эффективность каналов связи ограничивается двумя факторами:

размером и стоимостью аппаратуры кодирования/декодирования;

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

Эти коды используют для:

исправления ошибок — корректирующие коды;

Корректирующие коды основаны на введении избыточности.

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

Алгебраические коды подразделяются на два класса:

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

При кодировании неразделимыми кодами разделить символы входной последовательности на информационные и проверочные невозможно (10, "https://referat.bookap.info").

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

Общие принципы использования избыточности.

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

На вход кодирующего устройства поступает последовательность из k информационных двоичных символов. На выходе ей соответствует последовательность из n двоичных символов, причем n>k.

Всего может быть 2 k различных входных и 2 n различных выходных последовательностей.

Из общего числа 2 n выходных последовательностей только 2 k последовательностей соответствуют входным. Их называют разрешенными кодовыми комбинациями.

Остальные (2 n -2 k ) возможных выходных последовательностей для передачи не используются. Их называют запрещенными кодовыми комбинациями.

Искажения информации в процессе передачи сводятся к тому, что некоторые из передаваемых символов заменяются другими — неверными.

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

2 k случаев безошибочной передачи;
2 k (2 k -1) случаев перехода в другие разрешенные комбинации, что соответствует необнаруженным ошибкам;
2 k (2 n — 2 k ) случаев перехода в неразрешенные комбинации, которые могут быть обнаружены.

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

Пример: Определим обнаруживающую способность кода, каждая комбинация которого содержит всего один избыточный символ (n=k+1).

1. Общее число выходных последовательностей составляет 2 n =2 k+1 , т. е. вдвое больше общего числа кодируемых входных последовательностей.
2. За подмножество разрешенных кодовых комбинаций можно принять, например, подмножество 2 k комбинаций, содержащих четное число единиц (или нулей).
3. При кодировании к каждой последовательности из k информационных символов добавляют один символ (0 или 1), такой, чтобы число единиц в кодовой комбинации было четным. Изменение (в процессе передачи) любого нечетного числа символов переводит разрешенную кодовую комбинацию в подмножество запрещенных комбинаций, что обнаруживается на приемной стороне по нечетности числа единиц. Часть опознанных ошибок составляет

Любой метод декодирования можно рассматривать как правило разбиения всего множества запрещенных кодовых комбинаций на 2 k пересекающихся подмножеств M_i, каждая из которых ставится в соответствие одной из разрешенных комбинаций. При получении запрещенной комбинации, принадлежащей подмножеству M_i, принимают решение, что передавалась запрещенная комбинация A_i. Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из A_i, т. е. 2 n -2 k cлучаях.

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

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

Способ разбиения на подмножества зависит от того, какие ошибки должны направляться конкретным кодом.

Читайте также: