Все о моделировании в Компас-3D LT
   Главная Статьи Файлы Форум Ссылки Категории новостей
December 04 2024 11:51:21   
Навигация
Главная
Статьи
Файлы
FAQ
Форум
Ссылки
Категории новостей
Обратная связь
Фото галерея
Поиск
Разное
Карта Сайта
Популярные статьи
Что необходимо ... 65535
4.12.1 Професси... 34308
Учимся удалять!... 32284
Примеры, синони... 23600
Просмотр готовы... 22895
Декартовы коорд... 22594
FAST (методика ... 21631
содержание - се... 20948
Просмотр готовы... 19659
Работа с инстру... 15098
Сейчас на сайте
Гостей: 1
На сайте нет зарегистрированных пользователей

Пользователей: 9,955
новичок: Logyattella
Друзья сайта
Ramblers Top100
Рейтинг@Mail.ru

Реклама
Выполняем курсовые и лабораторные по разным языкам программирования
Подробнее - курсовые и лабораторные на заказ по Delphi
Turbo Pascal, Assembler, C, C++, C#, Visual Basic, Java, GPSS, Prolog
2.4.3 Блоковые коды
Способность кода обнаруживать и исправлять ошибки обусловлена наличием избыточных символов. На вход кодирующего устройства поступает последовательность из k информационных символов. На выходе ей соответствует последовательность из n двоичных символов, причём n>k. Всего может быть 2k различных входных и 2n различных выходных кодовых комбинаций. Из общего числа 2n выходных последовательностей только2k соответствуют входным. Эти комбинации называют разрешимыми.
Остальные 2n - 2k возможных выходных последовательностей для передачи не используются. Искажение информации в процессе передачи сводится к тому, что некоторые из передаваемых символов заменяются другими – неверными. Так как каждая из 2k разрешённых комбинаций в результате действия помех может трансформироваться в любую другую, то всего имеется 2k *2n возможных случаев передачи. В это число входят:
- 2k случаев безошибочной передачи;
- 2k (2k –1) случаев перехода в другие разрешённые комбинации, что соответствует необнаруживаемым ошибкам;
- 2k (2n -2k )случаев перехода в неразрешённые комбинации, которые могут быть обнаружены.
Следовательно, часть обнаруживаемых кодовых комбинаций от общего числа составляет:

. (2.4.1)

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

10011101
11000101
01011000 , d=3.

Минимальное расстояние, взятое по всем парам кодовых разрешённых комбинаций, называется минимальным кодовым расстоянием. Декодирование после приёма может производиться таким образом, что принятая кодовая комбинация отождествляется с той разрешённой, которая находится от неё на наименьшем кодовом расстоянии. Такое декодирование называется декодированием по методу максимального правдоподобия.
Очевидно, что при d=1 все кодовые комбинации являются разрешёнными. Любая одиночная ошибка трансформирует данную комбинацию в другую разрешённую комбинацию. Это случай безызбыточного кода, не обладающего корректирующей способностью. Если d=2, то ни одна из разрешённых кодовых комбинаций при одиночной ошибке не переходит в другую разрешённую кодовую комбинацию. Код обнаруживает одиночные ошибки, а также другие ошибки нечётной кратности. В общем случае, при необходимости обнаруживать ошибки кратности до r включительно, минимальное Хеммингово расстояние должно быть, по крайней мере, на единицу больше r

. (2.4.2)

Для исправления одиночной ошибки каждой разрешённой комбинации необходимо сопоставить подмножество запрещённых кодовых комбинаций. Чтобы эти подмножества не пересекались, хеммингово расстояние между разрешёнными кодовыми комбинациями должно быть не менее трёх. При n=3 за разрешённые кодовые комбинации можно принять 000 или 111. тогда разрешенной кодовой комбинации 000 необходимо приписать подмножества запрещённых кодовых комбинаций 001, 010, 100, образующиеся в результате возникновения одиночной ошибки в комбинации 000. Подобным же образом комбинации 111 необходимо приписать подмножества запрещённых кодовых комбинаций: 110, 011, 101. образующиеся в результате одиночной ошибки в комбинации 111.
В общем случае для обеспечения возможности исправления всех ошибок кратности до s включительно при декодировании по методу максимального правдоподобия каждая из ошибок должна приводить к запрещённой комбинации, относящейся к подмножеству исходной разрешённой кодовой комбинации. Поскольку указанные подмножества не должны пересекаться, минимальное хеммингово расстояние между разрешёнными кодовыми комбинациями должно удовлетворять соотношению:

. (2.4.3)

Нетрудно убедиться в том, что для исправления всех ошибок кратности s и одновременно обнаружения всех ошибок кратности r  s минимальное хеммингово расстояние нужно выбирать из условия:

. (2.4.4)

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

; (2.4.5)
. (2.4.6)

Коды, обеспечивающие заданную корректирующую способность при минимально возможной избыточности, называются оптимальными. Найдём для оптимального кода величину Q – наибольшее возможное число разрешённых комбинаций n- значного двоичного кода, обладающего способностью исправлять взаимно независимые ошибки кратности до s включительно. Это равносильно отсеканию числа комбинаций, кодовое расстояние между которыми не менее d=2s+1.
Общее число различных исправляемых ошибок для каждой разрешённой комбинации составляет:

. (2.4.7)

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

. (2.4.8)

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


, (2.4.9)
или

. (2.4.10)
Эта верхняя оценка найдена Хеммингом. Коды, для которых в приведённом соотношении достигается равенство, называются плотноупакованными.
Комментарии
Нет комментариев.
Добавить комментарий
Пожалуйста залогиньтесь для добавления комментария.
Рейтинги
Рейтинг доступен только для пользователей.

Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.

Нет данных для оценки.
Гость
Имя

Пароль



Вы не зарегистрированны?
Нажмите здесь для регистрации.

Забыли пароль?
Запросите новый здесь.
Случайные статьи
До 200 долларов
1.2 СТРУКТУРА СИСТЕМЫ
СИСТЕМНЫЕ ОПЕРАЦИИ
Экран
1.3.1 Первичная с...
Преимущества испол...
Подтип сущности
Окончание работы с...
2.4.2 Логическое к...
10.3.1 Символьные ...
7.3.2. Концепци...
Группа 3 — програм...
7.11 УПРАЖНЕНИЯ
Носимые аппараты
11.3 ВЗАИМОДЕЙСТВ...
Принцип действия
ВТОРОЙ ПРИМЕР
10.1.2.6 Другие фу...
Как показывать мод...
Светофоры
Аннотация
Реинжиниринг бизне...
Фрагмент [КОМПАС-3...
7.4. Организационн...
Батарея
Канал (канал связи)
Глава 12. BOTTOM L...
10.4 ПОТОКИ
Чтение названий ат...
Что для нас будет ...
Текст
Характеристики сон...
Бенчмаркинг процес...
4.10 УПРАЖНЕНИЯ
10.1.2.5 Ioctl
9.3 СИСТЕМА СМЕША...
Может это сущность ?
БИБЛИОГРАФИЯ
Глава пятая. ВЫВО...
9.2.4 Замещение ст...
Мини-чат
Вам необходимо залогиниться.

Нет присланных сообщений.
Copyright © 2009