Добавил:

Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Ижевский государственный технический университет им. М. Т. Калашникова

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

tes-slides-04

.pdf

Скачиваний:

Добавлен:

12.03.2015

Размер:

912.6 Кб

Скачать

☆

1 / 21 2 > Следующая >>>

						3.1. Введение
						3.1. Введение
	А.В. Абилов					Типыошибок

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

	Обнаружение и исправление ошибок					необходимы функции обнаружения и/или коррекции ошибок

			Типы ошибок:
	Для студентов заочной формы обучения		Типы ошибок:
	Для студентов заочной формы обучения					Одиночная ошибка (происходит инверсия одного двоичного символа)

					Пакетная ошибка (инвертируется несколько бит в блоке)
	E-mail: albert.abilov@mail.ru		Импульсная помеха – 0,01 с, скорость передачи данных – 1200 бит/с:
	E-mail: albert.abilov@mail.ru			инвертируется до 12 бит информации
	Web: http://www.istu.ru/unit/prib/net/edu/teach			инвертируется до 12 бит информации
	Web: http://www.istu.ru/unit/prib/net/edu/teach

2010	А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"	1	2010			А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"	2

3.1. Введение

Типыошибок: одиночнаяошибка

Типыошибок: пакетнаяаяошибкаошибка

При одиночной ошибке инвертируется лишь один бит в блоке данных

При пакетной ошибке инвертируется два или более бит в блоке данных

Инверсия бита

Длина пакетной

Передаваемый

ошибки (8 бит)

блок

Искаженные биты

Передаваемый блок

Принимаемый блок

не обязательно

Искаженные биты

Рис. 3.1. Одиночная ошибка

следуют друг за

Посылаемый блок (код): 00000010 (ASCII STX) – Start of text (Начало текста)

другом

Принимаемый блок (код): 00001010 (ASCII LF) – Line feed (Перевод строки)

Принимаемый блок

Рис. 3.2. Пакетная ошибка длинной 8 бит

Одиночные ошибки менее вероятны по сравнению с пакетными ошибками

Длина пакетной ошибки: от первого до последнего искаженного бита,

При скорости передачи данных 1 Мбит/с, длительность бита равна лишь 1 мкс

определяется скоростью передачи данных и длительностью помехи

Большинство помех имеет значительно большую длительность

Пакетные ошибки более вероятны по сравнению с одиночными ошибками

Скорость передачи 1 кбит/с, длит. помехи 0,01 с – искажаются до 10 бит

Скорость передачи 1 Мбит/с, длит. помехи 0,01 с – искажаются до 10000 бит

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.1. Введение

Контрольошибокиизбыточность(Redundancy)

Кодирование(Coding)

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

Для обнаружения или исправления ошибок к блоку полезной

информации добавляется избыточность (добавочные биты)

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

проверяется соотношение полезной и избыточной комбинации

По избыточным битам на приемной стороне обнаруживаются или исправляются

Приемник

Передатчик

искаженные биты информации

Обнаружение ошибок (Error Detection): определяется лишь факт наличия

Да

Данные

ошибок, при этом их тип (одиночная или пакетная ошибка), количество и

Потеря

место положение не имеют значения

данных

Нет

Исправление ошибок (Error Correction): определяется точное количество

искаженных бит и их местоположение в блоке

Прямое исправление ошибок (Forward error correction – FEC): поврежденный

Информация и

избыточность

блок восстанавливается с помощью избыточности (исправить можно

ограниченное количество ошибок)

Рис. 3.3. Кодирование

Ретрансляция (Retransmission): при обнаружении ошибок в блоке

Две разновидности схем кодирования:

запрашивается его повторная передача

Блочное кодирование

Сверточное кодирование

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

		3.1. Введение					3.1. Введение
		3.1. Введение					3.1. Введение
		Модульнаяарифметика(Modular Arithmetic)					Арифметикапомодулюю22 ((ModuloModulo--22 ArithmeticArithmetic))
Одна из функций кодирования и декодирования: операции сложения и					Арифметика по модулю 2: используется в большинстве случаем при передаче
	умножения в соответствии с правилами для алгебраического поля с					данных				+	0	1	•	0	1
	ограниченным количеством элементов					Примеры таблиц сложения и умножения для GF(2)				+	0	1	•	0	1
	ограниченным количеством элементов					Примеры таблиц сложения и умножения для GF(2)				0	0	1	0	0	0
Поле Галуа: алгебраическое поле с q элементами – GF(q):										0	0	1	0	0	0
Поле Галуа: алгебраическое поле с q элементами – GF(q):										1	1	0	1	0	1
	Для двоичной системы счисления q = 2 (элементы 0 и 1)
	Простейшее поле – это поле GF(2)					Операция сложения (и вычитания) по модулю 2 соответствует операции XOR
	В общем случае если q – простое целое число, ограниченное поле GF(q) состоит						(исключающее ИЛИ). Примеры операции XOR:
		из элементов {0, 1, …, q – 1}
	Операции сложения и умножения над элементами из GF(q) осуществляется по
		модулю q
								Два одинаковых бита: результат – 0

		В арифметике по модулю q используются только целые числа
		в диапазоне от 0 до q–1, включительно
		в диапазоне от 0 до q–1, включительно						Два разных бита: результат – 1	Операция XOR для двух слов
								Рис. 3.4. Операция XOR
								Рис. 3.4. Операция XOR
						Если оба элемента одинаковы – результат 0; если элементы разные – результат 1

2010		А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"	7	2010				А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"							8

3.2. Блочноекодирование

3.2. Блочноекодированиерование

k бит

Информационное слово (Dataword): блоки длиной k бит, на которые делится

2k комбинаций информационных слов длиной k бит

Блочное кодирование:

Компенсирует недостатки

исходная двоичная информационная последовательность

n бит

Избыточные символы (Redundancy): добавляются по определенному правилу

линейного кодирования

2n комбинаций кодовых слов длиной n бит (из них 2k разрешенных)

ненадежного физического

(r бит) к информационному слову на передаче

Рис. 3.5. Множества информационных и

уровня

Кодовое слово (Codeword): двоичный вектор (комбинация) фиксированной

кодовых слов в блочном кодировании

может использоваться как

длины n = k + r бит; формируется при блочном кодировании

для синхронизации, так и

Блочное кодирование (Block Coding):

Деление на

для обнаружения ошибок

Образуется множество из 2k информационных слов длиной k и множество из 2n

блоки

k бит

кодовых слов длиной n

Так как n > k, то количество комбинаций кодовых слов больше количества

Добавление

комбинаций информационных слов

n бит

избыт. бит

Блочное кодирование подразумевает взаимно-однозначное соответствие

информационных и кодовых слов

При кодировании не используются 2n – 2k кодовых слов

Линейное

Разрешенные слова (комбинации): комбинации, используемые при

кодирование

кодировании

Рис. 3.6. Блочное кодирование

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.2. Блочноекодирование

3.2. Блочноекодированиерование

Обнаружениеошибок

Пример1 Рассмотрим блочный код 4B/5B : исходная информационная последовательность

Два условия возможности обнаружения искажений в кодовом слове:

двоичных символов делится на информационные слова длиной k = 4 бит. Кодер

Приемник обладает списком разрешенных комбинаций кодового слова

заменяет каждое слово на соответствующее кодовое слово длиной n = 5 бит

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

k = 4

Разрешенные слова

n = 5

разрешенных комбинаций

Передатчик

Приемник

Кодер

Декодер

Информация

Извлечение

Генератор

Детектор

Потеря

Рис. 3.7. Замена комбинаций

в блочном кодировании

Множество из 16 комбинации информационного слова отображается лишь на часть

Информационная и

Ненадежная передача

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

Принятый код

избыточность

Каждый код должен содержать не более одного нулевого бита вначале кода (слева) и не

Рис. 3.8. Обнаружение ошибок в процессе блочного кодирования

более двух нулевых бит в конце (справа)

кодовые слова не могут содержать более чем три последовательных нулевых бита, что

Если кодовое слово не приеме принадлежит одной из разрешенных комбинаций,

облегчает тактовую синхронизацию

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

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.2. Блочноекодирование

3.2. Блочноекодированиерование

Обнаружениеошибок

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

Пример2

Для исправления ошибок требуется определить, какая конкретно комбинация

Запрещенная

передавалась

Примем k = 2 и n = 3:

Табл. 3.1

комбинация

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

Кодирование для обнаружения ошибок

(обнаружение

ошибки)

Пример3

Информационное слово

Кодовое слово

111

000

Примем k = 2 и n = 5:

Табл. 3.2

011

Верно

011

Кодирование для исправления ошибок

Запрещенная

101

Информационное слово

Кодовое слово

000

комбинация

110

Разрешенная

00000

01001

01011

комбинация

10101

Пусть инф. слово 01 кодируется в кодовое слово 011, рассм. три случая:

(ложный прием)

11110

1. Получатель принимает 011, что является верным, и извлекает из него информационных

код 01

Пусть информационное слово 01 кодируется в кодовое слово 01011:

2. Кодовое слово искажается и принимается комбинация 111 (бит слева искажен). Такой

Второй бит справа искажается, принимается комбинация 01001

разрешенной комбинации не существует и код отбрасывается

Принятое слово 01001 сравнивается со всеми разрешенными и определяется количество

3. Кодовое слово искажается и принимается комбинация 000 (два бита справа искажены).

различных бит

Извлекается неверное информационное слово 00

Комбинация отличающаяся не более чем на один бит – верная (01011)

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.2. Блочноекодирование

3.2. Блочноекодированиерование

РасстояниеХэмминга

Минимальноерасстояниение ХэммингаХэмминга

Расстояние Хэмминга: определяется количеством различий между

Минимальное расстояние Хэмминга dmin: определяется как наименьшее

соответствующими битами в словах

расстояние Хэмминга между всеми возможными парами комбинаций кода

Обозначается d(x, y), x и y – слова одинаковой длины

Минимальное расстояние Хэмминга определяется как наименьшее расстояние

Определяется операцией XOR ( ) над двумя словами и подсчетом количества

Хэмминга между всеми возможными парами на множестве комбинаций кода

единиц в результате

Пример5

Вес кодового слова: это количество единиц в кодовом слове

Информационное слово

Кодовое слово

Найти минимальное расстояние Хэмминга для

000

Расстояние Хэмминга между двумя словами определяется как количество

кода из таблицы:

011

различий между одноименными битами (вес результата XOR)

101

Пример4

110

Расстояние Хэмминга между словами:

Решение

Расстояние Хэмминга d(000, 011) равно 2, так как 000 011 = 011 (два единичных символа

в слове).

Находим расстояния Хэмминга между всеми парами комбинаций в слове :

Расстояние Хэмминга d(10101, 11110) равно 3, так как 10101 11110 = 01011 (три

d(000, 011) = 2;

d(000, 101) = 2;

d(000, 110) = 2;

единичных символа в слове).

d(011, 101) = 2;

d(011, 110) = 2;

d(101, 110) = 2;

dmin = 2

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.2. Блочноекодирование

3.2. Блочноекодированиерование

МинимальноерасстояниеХэмминга

Минимальноерасстояниение ХэммингаХэмминга

Пример6

Информационное слово

Кодовое слово

Связь корректирующей способности кода с расстоянием Хэмминга

00000

Найти минимальное расстояние Хэмминга

Расстояние Хэмминга между принятым и переданным кодовыми словами точно

01011

для кода из таблицы:

соответствует количеству искаженных бит

10101

Например, передается 00000, а принимается 01101. Три бита искажены и расстояние

11110

Решение

Хэмминга равно d(00000, 01101) = 3

Минимальное расстояние Хэмминга при обнаруженииобнаруженииошибокошибок

Находим все возможные расстояния Хэмминга для кода из табл.:

d(00000, 01011) = 3;

d(00000, 10101) = 3;

d(00000, 11110) = 4;

При необходимости обнаружения вплоть до to ошибок минимальное расстояние

d(01011, 10101) = 4;

d(01011, 11110) = 3;

d(10101, 11110) = 3;

между разрешенными кодовыми словами должно быть dmin ≥ to + 1. В этом случае

dmin = 3

ошибки в кодовом слове не приводят к его трансформации в одну из разрешенных

комбинаций, т.к. их не достаточно

Три основных параметра кодирования: длина кодового слова n; длина

Условие dmin ≥ to + 1 дает гарантированное обнаружение вплоть до to ошибок в слове

Если ошибок в принимаемом слове больше to, то они также могут быть обнаружены

информационного слова k; минимальное расстояние Хэмминга dmin

но не гарантированно (не для всех комбинаций)

Форма записи схемы кодирования: C(n, k) с dmin

Примеры записи: для Примера 5: C(3, 2) с dmin = 2;

Для гарантированного обнаружения вплоть до s ошибок в кодовом слове

для Примера 6: C(5, 2) с dmin = 3

минимальное расстояние Хэмминга должно быть dmin ≥ to + 1

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.2. Блочноекодирование

3.2. Блочноекодированиерование

МинимальноерасстояниеХэмминга

Минимальноерасстояниение ХэммингаХэмминга

Пример7

Принцип обнаружения ошибок можно посредством геометрического представления

Информационное

Кодовое слово

Минимальное расстояние Хэмминга для кода из

расстояния Хэмминга

слово

таблицы равно 2

000

Гарантируется обнаружение только одной ошибки

011

При двух ошибках возможен переход в другую

Обозначения

101

разрешенную комбинацию

Радиус to

Любое разрешенное слово

110

Любое запрещенное слово с

Пример8

количеством ошибок от 1 до to

Информационное

Кодовое слово

Минимальное расстояние Хэмминга для кода из

слово

таблицы равно 3

00000

dmin > to

Гарантируется обнаружение до двух ошибок, т.к.

01011

Рис. 3.9. Обнаружение ошибок в процессе блочного кодирования

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

10101

Если передаваемое кодовое слово

x представить как центр окружности

комбинацию

11110

радиусом to, то все принимаемые кодовые слова с количеством ошибок от 1 до to

Некоторые комбинации трех ошибок создают

разрешенную комбинацию (ошибки не

можно

представить в виде точек в

пределах круга и на линии окружности

(пространства запрещенных комбинаций). Все остальные (разрешенные кодовые

обнаруживаются)

комбинации) должны находиться вне круга

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.2. Блочноекодирование							3.2. Блочноекодированиерование
МинимальноерасстояниеХэмминга							Минимальноерасстояниение ХэммингаХэмминга
Минимальное расстояние Хэмминга при исправленииошибок							Так как две области соседних пар разрешенных кодовых слов не должны
Исправление ошибок может основываться на понятии области, окружающей							перекрываться, то dmin должно быть больше 2tи. Следовательно dmin ≥ 2tи + 1
кодовое слово (множества). Все множество запрещенных комбинаций							Для гарантированного исправления вплоть до tи ошибок в кодовом слове
разбивается на непересекающиеся подмножества радиусом tи, каждое из которых
ставится в соответствие одной из разрешенных комбинаций (в центре)							минимальное расстояние Хэмминга должно быть dmin ≥ 2tи + 1
Область для слова x		Область для слова y					Для исправления до tи ошибок и одновременного обнаружения до tо ошибок (при
							tо ≥ tи) минимальное расстояние должно удовлетворять условию dmin ≥ tо + tи + 1
	Радиус tи	Радиус tи		Обозначения
	Радиус tи	Радиус tи		Любое разрешенное слово			Пример9
				Любое запрещенное слово с
				количеством ошибок от 1 до tи
				количеством ошибок от 1 до tи			Схема кодирования имеет минимальное расстояние Хэмминга dmin = 4. Какова

							обнаруживающая и исправляющая способность такой схемы?
	dmin > 2tи						Решение
Рис. 3.10. Исправление ошибок в процессе блочного кодирования							Решение
							Код гарантирует обнаружение вплоть до трех ошибок (tи = 2) и гарантирует исправление до
Если кодовое слово имеет tи ошибок или меньше, то оно располагается в пределах
							одной ошибки (tи = 2)
круга или на окружности. Если принимается искаженное слово, принадлежащее							Исправляющие коды должны иметь нечетное минимальное расстояние Хэмминга
области для слова x, то x – это оригинальное кодовое слово
2010	А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"					21	2010	А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"				22
3.3. Линейныеблочныекоды							3.3. Линейныеблочныеочныекодыкоды
							Минимальноерасстояниение ХэммингаХэмминга длядлялинейныхлинейныхблочныхблочныхкодовкодов
Линейные блочные коды: это коды, для которых операция XOR двух							Минимальное расстояние Хэмминга для линейных блочных кодов: это
разрешенных кодовых слов дает другое разрешенное кодовое слово							минимальный вес кодового слова среди всех ненулевых разрешенных
В линейных блочных кодах операция XOR над любой парой разрешенных							кодовых слов
	комбинаций дает другую разрешенную комбинацию						Пример11
Пример10							Пример11
Пример10							Определить минимальные расстояния Хэмминга для кодовых слов в таблицах?
Принадлежат ли кодовые слова в таблицах к классу линейных блочных кодов?:
В обоих случаях результат операции XOR над любой парой комбинаций в кодовых								dmin = 2			dmin = 3
словах является разрешенной комбинацией. Принадлежат в обоих случаях								dmin = 2			dmin = 3
							Информационное	Кодовое слово		Информационное	Кодовое слово
							Информационное	Кодовое слово		Информационное	Кодовое слово
Информационное	Кодовое слово						слово			слово
Информационное	Кодовое слово		Информационное	Кодовое слово			00	000		00	00000
слово			слово				00	000		00	00000
слово			слово				01	011	2	01	01011	3
00	000		00	00000			01	011	2	01	01011	3
00	000		00	00000			10	101	2	10	10101	3
01	011		01	01011			10	101	2	10	10101	3
01	011		01	01011	=		11	110	2	11	11110	4
10	101		10	10101	=		11	110	2	11	11110	4
10	101	=	10	10101
11	110	=	11	11110
11	110		11	11110						Вес кодового
							Код с проверкой			Вес кодового
							Код с проверкой			слова
							четности			слова
							четности
2010	А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"					23	2010	А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"				24

3.3. Линейныеблочныекоды

Примеры: кодспростойпроверкойчетности

C(5, 4)

Код с простой проверкой четности:

наиболее простой и достаточно известный код с обнаружением ошибок

Информационное слово k бит преобразуется в кодовое слово n = k + 1 бит

Бит четности (добавляемый бит) выбирается так, чтобы вес кодового слова был четным

Минимальное расстояние Хэмминга dmin = 2, следовательно код может обнаружить только одиночную ошибку и не может исправлять

Код C(5, 4) из таблицы является примером кода с простой проверкой четности

Инф-ное. слово	Кодовое слово
0000	00000

0001	00011

0010	00101

0011	00110

0100	01001

0101	01010

0110	01100

0111	01111

1000	10001

1001	10010

1010	10100

1011	10111

1100	11000

1101	11011

1110	11101

1111	11110

Код с простой проверкой четности - это код длиной n = k + 1 и dmin = 2, способный обнаружить одиночную ошибку в кодовом слове

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.3. Линейныеблочныекоды

Примеры: кодспростойпроверкойчетности

Формирование бита четности:

Бит четности r0 формируется побитным сложением информационного слова по модулю 2 и является результатом этого сложения:

r0 = a3 a2 a1 a0

Если вес информационного слова четный – r0 = 0, если нечетный – r0 = 1, следовательно, вес кодового слова всегда четный

Работа декодера схемы простой проверки четности:

Детектор декодера, также как и генератор, осуществляет побитную операцию

сложения по модулю 2, но над элементами принимаемого кодового слова {q0, b0, b1, b2, b3} . Результатом является один бит и называется синдром:

s0 = b3 b2 b1 b0 q0

Если вес принимаемого кодового слова четный – s0 = 0, если нечетный – s0 = 1, следовательно, вес кодового слова всегда четный

Устройство решения анализирует полученный синдром, если s0 = 0, то ошибок нет и кодовое слово принимается, если s0 = 1, слово отклоняется

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.3. Линейныеблочныеочныекодыкоды

Примеры: кодспростойойпроверкойпроверкойчетностичетности

Передатчик

Приемник

Кодер

Декодер

Информационное слово

Принять

Отклонить

Синдром

Логика

решения

Генератор

Детектор

Бит четности

Ненадежная

передача

Кодовое слово

Рис. 3.11. Кодер и декодер для кода с простой проверкой четности

Работа кодера схемы простой проверки четности:

Генератор кодера на основе анализа информационного слова {a0, a1, a2, a3} формирует бит четности r0, чтобы вес кодового слова был четным

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.3. Линейныеблочныеочныекодыкоды

Примеры: кодспростойойпроверкойпроверкойчетностичетности

Пример12

Пусть передатчик посылает информационное слово 1011 и формирует кодовое слово 10111, которое посылается приемнику. Рассмотрим 5 сценариев:

1.Ошибок нет. Принимаемое кодовое слово 10111, синдром 0, извлекается информационное слово 1011

2.Одиночная ошибка в символе a1. Принимаемое кодовое слово 10011, синдром 1, кодовое слово отклоняется

3.Одиночная ошибка в символе r0. Принимаемое кодовое слово 10110, синдром 1, кодовое слово отклоняется (не смотря на то, что информационное слово не искажается)

4.Два ошибочных символа: r0 и a3. Принимаемое кодовое слово 00110, синдром 0, приемник извлекает неверное информационное слово 0011. Декодер не способен обнаружить четное количество ошибок в кодовом слове

5.Три ошибочных символа: a3, a2, a1. Принимаемое кодовое слово 01011, синдром 1, кодовое слово отклоняется. Декодер гарантирует обнаружение одиночной и нечетного количества ошибок в слове

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

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.3. Линейныеблочныекоды

3.3. Линейныеблочныеочныекодыкоды

Примеры: кодсдвойнойпроверкойчетности

Примеры: кодсдвумернойнойпроверкойпроверкойчетностичетности

Код с двойной проверкой

Информационные слова

четности:

четности рядам

Блоки инф. данных

формируются в

Биты по

таблицу

Для каждого блока

Биты четности

данных (ряда)

по столбцам

вычисляется бит

Одиночная ошибка повлияла на два бита четности

Две ошибки повлияли на два бита четности

четности

Затем для каждой

колонки вычисляется

Кодовые слова с битами четности

бит четности

Рис. 3.12. Код с двойной проверкой четности

формируется дополнительный ряд в таблице (биты четности по столбцам)

вся таблица передается кодовыми словами

	Код с двойной проверкой четности гарантированно обнаруживает до трех
				Три ошибки повлияли на четыре бита четности		Четыре ошибки повлияли на четыре бита
					четности (ошибки не обнаружены)
	любых ошибочных бит				четности (ошибки не обнаружены)
	любых ошибочных бит			Рис. 3.13. Примеры обнаружения ошибок в коде с двойной проверкой четности


2010	А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"	29	2010	А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"			30

				3.3. Линейныеблочныекоды				3.3. Линейныеблочныеочныекодыкоды
				3.3. Линейныеблочныекоды				3.3. Линейныеблочныеочныекодыкоды
				Примеры: кодыХэмминга				Примеры: кодХэммингага СС(7,(7, 4)4)											CC((77,, 4)4)
								Передатчик								Приемник		Информа-	Кодовое
	Коды Хэмминга: относятся к категории корректирующих кодов							Передатчик								Приемник		Информа-	Кодовое
																		ционное	слово
										Кодер		Декодер
						Информационное слово				Кодер		Декодер			Информационное слово
			Существуют коды Хэмминга для исправления одной ошибки (dmin = 3) или															слово



																		0000	0000000
				исправления одной и обнаружения до двух ошибок в слове (dmin = 4)
																		0001	0001101
			Если длина кодового слова n = k + r , то r бит должны указывать по крайней
																	Логика	0010	0010111
				мере на k + r + 1 различных состояний (одно – нет ошибок, остальные – k + r													решения
																		0011	0011010
													Синдром					0011	0011010
				позиции ошибки в слове)
				позиции ошибки в слове)														0100	0100011
									Генератор
				r бит образует 2r комбинаций, следовательно должно выполняться 2r ≥ k + r + 1					Генератор					Контроллер				0101	0101110
																		0101	0101110
	Неравенство Хэмминга: необходимое количество проверочных бит																	0110	0110100

																		0111	0111001
				для исправления одиночной ошибки (для dmin = 3) составляет n – k ≥ log (n + 1),														0111	0111001
											Ненадежная							1000	1000110
			для исправления одиночной и обнаружения до двух ошибок (для dmin = 4)								передача
																		1001	1001011
																		1001	1001011
				составляет n – k ≥ log (n) + 1			Кодовое слово										Кодовое слово
							Кодовое слово										Кодовое слово	1010	1010001
								Рис. 3.14. Кодер и декодер для кода Хэмминга

			Примеры кодов Хэмминга для dmin = 3 : C(7, 4), C(11, 7), C(15, 11), C(31, 26) и др.
																		1011	1011100
						Работа кодера и декодера в схеме кода Хэмминга:												1011	1011100
			Примеры кодов Хэмминга для dmin = 4 : C(8, 4), C(12, 7), C(16, 11), C(32, 26) и др.			Работа кодера и декодера в схеме кода Хэмминга:												1100	1100101
								Генератор кодера по информационному слову формирует										1101	1101000
								Генератор кодера по информационному слову формирует										1101	1101000
								три избыточных бита четности r0, r1 и r2										1110	1110010
		Коды Хэмминга: исправление одной ошибки (dmin = 3, n = 2r – 1), исправление
								Контроллер декодера вычисляет синдром по принятому										1111	1111111
				одной и обнаружения двух ошибок (dmin = 4, n = 2r–1)

								кодовому слову, комбинация которого указывает на ошибку
								кодовому слову, комбинация которого указывает на ошибку

2010				А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"	31	2010				А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"									32

3.3. Линейныеблочныекоды

3.3. Линейныеблочныеочныекодыкоды

Примеры: кодХэммингаС(7, 4)

Примеры: кодХэммингага СС(7,(7, 4)4)

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

Вычисление синдрома:

Проверочную матрицу H для кода можно сформировать из матрицы размера

Контроллер декодера создает синдром, в котором каждый бит является

r × n для всех возможных комбинаций синдрома (за исключением нулевой)

проверкой четности для четырех из семи бит принимаемого кодового слова

перестановкой столбцов с одной единицей вправо:

Уравнения для обнаружителя аналогичны, но включают проверочные биты

n = 7

s0 = b3 b1 b0 q0

7 6 5 4 3 2 1

7 6 5 3

4 2 1

1 1 1 1 0 0 0

H =

1 1 1 0

1 0 0

D; E

s1 = b3 b2 b0 q1

r = 3

1 1 0 0 1 1 0

1 1 0 1

0 1 0

s2 = b3 b2 b1 q2

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

ошибки или ее наличие в одном из семи бит принимаемого кодового слова

Контрольные символы r0, r1 и r2 образуются из информационных символов с

Комбинация синдрома указывает на ошибку для ее исправления

помощью системы линейных уравнений rj = dj0a0 + dj1a1 +…+ djk-1ak-1, где dj =

Синдром

111

110

101

100

011

010

001

000

{0,1} – коэффициенты подматрицы D

Ошибка

Нет

Система проверочных линейных уравнений (без слагаемых с коэф. dj = 0)

r0 = a3 a1 a0

Проверочные биты располагаются не с краю кодового слова, а на номерах

r1 = a3 a2 a0

позиций степени двойки (20, 21, …, 2r–1 ), в этом случае синдром является

r2 = a3 a2 a1

двоичным представлением номера ошибочного элемента

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.3. Линейныеблочныекоды

3.3. Линейныеблочныеочныекодыкоды

Примеры: кодХэмминга

Позиция

Примеры: исправлениеепакетныхпакетныхошибокошибокдлядлякодакодаХэммингаХэмминга

С(7, 4)

бита

Принцип чередования бит:

Передача

Прием

Пример13

Значение

Несколько кодовых слов

Слово 4

Рассмотрим три сценария передачи информационных слов для кода Хэмминга:

группируются в блок,

1. Кодер преобразует информационное слово 0100 в кодовое слово 0101010. Принимается

формируется таблица из N

Слово 3

кодовое слово 0101010. Синдром равен 000 (нет ошибок), извлекается инф. слово 0100

строк (слов)

2. Кодер преобразует информационное слово 0111 в кодовое слово 0110100. Принимается

Слово 2

Биты передаются по

кодовое слово 0010100. Синдром равен 110 (ошибка в символе b2). Символ b2

столбцам слева с

инвертируется и извлекается информационное слово 0111

Слово 1

3. Кодер преобразует информационное слово 1101 в кодовое слово 1100110. Принимается

очередностью снизу вверх

кодовое слово 1010110. Синдром равен 011 (ошибка в символе b0). Символ b0

чередованием слов

инвертируется и извлекается неверное информационное слово 1010

Происходит

Пакетная ошибка

Пример14

перегруппировка бит при

Какова необходима избыточность r для кода Хэмминга, чтобы обеспечить длину

передаче

информационного слова по крайней мере 7 бит:

При возникновении

Блок передаваемых данных

Решение

пакетной ошибки длиной

Искаженные биты

Требуемая длина информационного слова: k = n – r ≥ 7. Длина кодового слова n = 2r – 1,

Рис. 3.15. Кодер и декодер для кода Хэмминга

до N бит в каждом слове

Длина информационного слова k = 2r – 1 – r ≥ 7.

искажается макс. 1 бит

При r = 3, k = 4 (k = 23 – 1 – 3 = 4) Длина информационного слова k ≥ 7 не обеспечивается

На приеме происходит обратная перестановка бит на исходные позиции в

При r = 4, k = 11 (k = 24 – 1 – 4 = 11) Длина информационного слова k ≥ 7 обеспечивается

кодовых словах

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.4. Циклическиекоды

Свойства циклических кодов :

Циклические коды являются разновидностью линейных блочных кодов

Если комбинация a0, a1, a2, …, an–1 является разрешенной, то комбинация, полученная путем циклического сдвига разрядов – an–1, a0, a1, …, an–2, тоже является разрешенной (циклический сдвиг разрешенного слова дает другое разрешенное слово)

Например, 1011000 – разрешенное кодовое слово, его сдвиг влево приводит к другому разрешенному слову

1 0 1 1 0 0 0 => 0 1 1 0 0 0 1

Бит последней позиции циклически переходит на первую позицию

Циклические коды способны корректировать ошибки

Циклический контроль четности с избыточностью (CRC) – широко распространенный метод контроля, используемый в циклических кодах

Широко используются с сетях передачи данных (например, LAN и WAN)

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.4. Циклическиекоды

Циклическийконтрольсизбыточностью (CRC)

Работа кодера схемы CRC:

Информационное слово наращивается до длины n справа дополнительными n – k нулями и подается на генератор

Генератор делит по модулю 2 полученное слово на заранее определенный делитель длиной n – k + 1 (длина остатка на один бит меньше делителя)

Частное отбрасывается, а остаток от деления r0, r1 и r2 дополняет справа информационное слово для образования кодового слова

Работа декодера схемы CRC:

Декодер принимает возможно искаженное кодовое слово и его копия подается в контроллер, который также производит деление по модулю 2 на тот же делитель

Полученный остаток от деления является синдромом длиной n – k, который поступает на логический анализатор

Если синдром нулевой, то левые k бит кодового слова принимаются как информационное слово, иначе отбрасываются

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.4. Циклическиекодыкоды

Циклический контролььссизбыточностьюизбыточностью ((CRCCRC))

Код циклической проверки с избыточностью (Cyclic Redundancy Check – CRC): пример кода C(7, 4)

Передатчик

Приемник

Кодер

Декодер

Информационное слово

Принять

Синдром

Отклонить

Логика

решения

Делитель

Генератор

Контроллер

Остаток

Ненадежная

передача

Кодовое слово

Рис. 3.16. Кодер и декодер для кода CRC (обнаружение ошибок)

CRCCRC кодкодCC((77,, 4)4)

Информа-	Кодовое
ционное	слово
слово
0000	0000000
0001	0001011
0010	0010110
0011	0011101

0100	0100111

0101	0101100

0110	0110001
0111	0111010
1000	1000101
1001	1001110

1010	1010011

1011	1011000

1100	1100010
1101	1101001
1110	1110100
1111	1111111

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

3.4. Циклическиекодыкоды

Циклический контролььссизбыточностьюизбыточностью ((CRCCRC))

Пример операции деления в кодере CRC:

Информационное

слово

Деление

Частное


Делитель		Делимое

Левый бит 0: делитель 0000

Остаток

Кодовое слово

Рис. 3.17. Деление в кодере CRC

Информационное слово 1001 делится пошагово на заранее определенный делитель 1011 (правый бит всегда 1)

Делитель вычитается (XOR) из первых четырех бит делимого, первый нулевой бит остатка отбрасывается

Полученный остаток (три бит) дополняется справа одним битом от делимого

Если на одном из шагов левый бит дополненного остатка нулевой, то используется нулевой делитель

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

2010

А.В. Абилов, Лекция 4. "Обнаружение и исправление ошибок"

1 / 21 2 > Следующая >>>

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

#
16.11.20192.32 Mб17Tema_3.2._Obekty_tekstovykh_dokumentov.doc
#
21.11.2018149.5 Кб4Tema_3.doc
#
27.11.2019330.46 Кб12Tenses.docx
#
12.03.20151.21 Mб79teor_system&syst_analiz_prakt.pdf
#
12.03.20151.03 Mб6tes-slides-03.pdf
#
12.03.2015912.6 Кб6tes-slides-04.pdf
#
22.03.201632.77 Кб17test_2.doc
#
23.12.2018496.64 Кб15Test_svodn_E_IzhGTU.doc
#
24.04.2019591.87 Кб4TGU.doc
#
07.05.2019129.54 Кб31THE ARTICLE.doc
#
12.11.201995.74 Кб1Theodor Storm Immensee.doc