16. Понятие вектора ошибки. Виды ошибок. Вероятность r-кратной ошибки в n-разрядном слове.
Вектор ош. – двоичн. кодовое слово такой же длины как исходное, содержащее ед-цы в тех разрядах, где произошло искажение содержимого код. слова. (код. слово и вектор ош. - абстракция). Воздействие помехи на слово заменяется слож-ем по mod2 исходн. слова с вектором ош.
Ошибки различают на некорректируемые и корректируемые.
Некорректир – при которых изменение содержимого в каком-то разряде слова не влияет на искажение содержимого в других словах.
При корректир – изменение содержимого под влиянием помех влечёт искажение содержимого некоторых других разрядах.
Различают ош. разной кратности:
1)однократные,
2)двукратные,
3)r-кратные (одновременное искажение содержимого в r- разрядах).
Однократная ошибка вызывает искажение содержимого только 1 разряда слова и т.д.
Вероятность r-кратной ошибки в n-разрядном слове:
-кол-во
таких ошибок
Вероятность такого события – вероятность сложного события и определяется произведение следующих множителей: вероятности, что искажение произойдет в этом разряде p, т.к. таких разрядов r и события независимые, то - pr , вероятности, что в остальных (n-r) разрядах искажения не будет определяется как (1-p)(n-r) , умноженных на количество возможных r-кратных ошибок. Т.о.
P=
17. Формулы для определения числа избыточных разрядов и границы Хэмминга для оптимальных корректирующих кодов; их суть и связь, примеры использования.
Пусть имеем n-разр. слова, требуется исправлять ошибкки вплоть до кратности S. Определим, какое мн-во разреш-х код. слов можно выделить на мн-ве всех n-разр-х слов. Для каждой исправляемой ош-ки. соотв-щее ей запрещ. код. слово. Поэтому «вокруг» каждого разреш. слова должны сгруппироваться те запрещ. слова, ош-ки кот-х подлежат исправлению. Поэтому кол-во запрещ. слов. не <, чем число исправл-ых ошибок.
2k-1>=Q
– определяется число информационных
разрядов; 2n-k-1>=n
– определяется число разрядов
помехоустойчивого слова; n-k=m
- определяется число избыточных разрядов;
– определяется граница Хемминга.
Дополнительных разрядов в кодовом слове
должно быть столько, чтобы породить
нужное число запрещенных слов или
классов смежности, а именно 2n-k-1.
Число классов смежности должно быть не
меньше, чем число исправляемых ошибок,
поэтому – 2n-k-1>=n
Пример: Пусть для построения кода, корректирующего все однократные ошибки, используются однобайтовые слова. Требуется определить максимальное число разрешенных слов, выбираемых из всего множества однобайтовых слов.
Число
однократных ошибок
,
т.е.
.
Максимальное
число разрешенных слов
,т.е.
18. Построение группового корректирующего кода (на примере).
Пример:
тип исправляемых ошибок - некоррелированные;
кратность
- S
= 1,
=15.
Процедура состоит из четырех этапов.
1. Расчет числа информационных и избыточных разрядов:
;
k = 4;
n = 7;
n - k =3;
где k - число информационных разрядов;
n - число избыточных разрядов;
2. Построение таблицы опознавателей ошибок.
Каждой ошибке соответствует собственный опознаватель.
|
Векторы ошибок а7 а6 а5 а4 а3 а2 а1 |
опознаватели (данный код) код Хемминга |
|
1 0 0 0 0 0 0 |
111 |
|
0 1 0 0 0 0 0 |
110 |
|
0 0 1 0 0 0 0 |
101 |
|
0 0 0 1 0 0 0 |
100 |
|
0 0 0 0 1 0 0 |
011 |
|
0 0 0 0 0 1 0 |
010 |
|
0 0 0 0 0 0 1 |
001 |
n = 7 n - k =3
3. Определение проверочных равенств.
1 - й (младший) - а1 а3 а6 а7 ;
2 - й - а2 а5 а6 а7 ;
3 - й - а1 а2 а4 а7 ;
При отсутствии однократных ошибок в слове дешифратор вычислит нулевой - опознаватель (состоящий из одних нулей - 000). Поэтому можно записать проверочные равенства дешифратора в виде следующей системы уравнений.
-
уравнения, формирующие 1-ый, 2-ой и 3-ий
разряды опознавателя.
4. Построение алгоритма кодирования.
Имея
данную систему уравнений на роль
избыточных разрядов следует выбирать
те, которые встречаются в проверочных
равенствах по одному разу, т.е.
.
Выделение избыточных разрядов
сопровождается определением информационных
разрядов помехоустойчивого кодового
слова. При этом для данного кода будут
помечены правила кодирования в виде:
