№35 (Коды с обнаружением и исправлением ошибок) (1006290)

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

Текст из файла

Коды с обнаружением и исправлением ошибок.

Коды Хэмминга

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

Обозначения:

U – информационная кодовая комбинация

X – код с исправляющими разрядами

G – порождающая матрица размерностью

H – контрольная матрица размерностью

- вектор

- вектор

инф. контр.

разряды разряды

Коды Хэмминга это системные коды.

, где S – синдром

- вектор столбец

S=0, если ошибки нет

S=1, в оставшихся случаях

Местонахождение ошибок определяется местонахождением столбца матрицы H совпадающим с синдромным вектором.

, то j – номер ошибочного разряда

преобразуется в H

доказательство

Пример:

n=7, U=4

A E

Пусть U=1010

Вводим ошибку:

1234567

X^* = 1110101

ошибка в этом разряде

Схемная реализация кодов Хэмминга.

1. Кодирование

0 1 0 1 1 0 1 0 0

1 0 1 0 U₂ U₃ U₄ U₁ U₃ U₄ U₁ U₂ U₄

U₁ U₂ U₃ U₄

M2

M2

M2

X₁ X₂ X₃ X₄

1 0 1 0 X₅ X₆ X₇

1 0 1

1. декодирование

ошибки нет

ДС

0

S_{1 1}

2

М2

3

S

М2

_{2 4}

М2

5

S

М2

_{3 6}

7

U₁ U₂ U₃ U₄

Кодирование циклическими кодами.

1. Кодирование не систематическими кодами

U(x) – информационный полином

g(x) – порождающий полином

V(x) – кодированный полином

Порождающий полином:

deg(g(x))=n-k deg – максимальная степень полинома

deg(V(x))=n-1

deg(U(x))=k-1

к – разрядность информационного полинома

Определение разрядностей или степеней полиномов производится по неравенству Хымминга:

r – разность исправляемых ошибок

Пример:

Пусть r=2, n=15

Тогда получим:

1+15+(15*14)/2=1+15+105=121

128, т.к берем ближайшее значение к 121

Требования к g(x):

в g(x) должны быть либо простейшие множители либо их произведения полинома xⁿ +1

Пример:

n=7

Тогда простейшими множителями будут:

1. Кодирование систематическим кодом

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

Параметры кода

Пусть n=7

Тогда в неравенстве Хэмминга будет

к – количество информационных разрядов

Порядок полинома:

deg(g(x))=k-1=3

deg(V(x))=n-1=6

deg(U(x))=n-k=3

Пример не симметрического кодирования

Пусть ,

Пример кодирования для систематического кода

Декодирование

- код с возможными ошибками

1 1

x x

x+1

Если нужно работать с двумя ошибками, то нужно написать в столбце следующее:

1 x

1 x²

………

1 x⁶

x x²

x x³

……..

x^n-1 xⁿ

Пример:

Систематический код

остаток ( ) по таблице

Метод сдвигов

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

Критерий сдвига

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

Пример:

Пусть

, значит код сдвигается в сторону старших разрядов.

Нужно осуществить сдвиг на три шага вперед

, h – число необходимых шагов

ост

Теперь нужно определить , для этого:

x+1

о ст 1

- это сдвинутый многочлен, но с исправленной ошибкой.

Теперь нужно осуществить сдвиг обратно. Нужно сделать 4 шага

Тогда

ост.

Остаток и будет скорректированным ответом

Коды БЧХ

(Боуз, Чоудхури, Хоквингем)

Позволяют исправлять большое количество ошибок.

Кодирование БЧХ

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

Рекомендуется:

n=2^k-1=3,7,15,31,…

Причем числа в таблице в 8-ричной записи. Перейдем в двоичную систему, позиционной записи к полиномиальной.

для этого перемножим сначала простые многочлены, т.о.

Теперь берем f₃ и переводим в двоичную систему, т.е. получаем 11111 и перемножаем с получившемся

Тогда имеем:

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

t – количество обнаруживаемых ошибок

к<15-10=5

Информационных разрядов будет к=5

Декодирование БЧХ

Теория поля имеет степенное и полиномиальное представление

Поле замкнуто, если

Алгоритм декодирования БЧХ

1. Синдромные элементы

, тогда

пусть , , , , ,

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

Переведем в степенную форму:

1. Определение фактического числа ошибок

Для этого используется определитель матрицы

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

При υ=3 получим

Следовательно, если , то фактически υ< υ начального.

Процесс продолжают до тех пор пока υ не будет равно 0 , т.е.

υ = υ-1=2

Отсюда следует, что υ = 2, т.е. в сообщение имеется 2 ошибки.

1. Определение локаторов ошибок

определитель матрицы

Тогда имеем уравнение для определения локализованных ошибок х₁ и х₂

( )

, отсюда следует

, т.е. ошибки

9

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

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

Список файлов ответов (шпаргалок)