Понятия минимального Хэммингова расстояния и его величина для кодов, обнаруживающих и исправляющих ошибки. Примеры.
Для определения степени различия м/у кодовыми словами вводится спец. метрика – кодовое или Хэммингово расст-е. Расст-е м/у 2мя код.словами опред-ся числом разрядов с различным содержимым. Мин Хэмм расст-е задаёт на мн-ве всех n-разр-х слов подмн-во разреш-х слов таких, что обычное Хэмм расст-е для каждой пары из них не меньше мин. Хэммингова.
Пример.пусть в кач-ве n-разр. слов используем все 3-х разр. 000...111. Если dmin=1,то все данные слова окажутся разрешёнными и нельзя будет исправить и обнаружить ош. Выберем из этого мн-ва разреш. такие, для кот-х dmin=2. 000,011,110,101. В случае 1-кратн. ош. любое из этих слов трансф-тся в запрещ-ое с нечётным числом ед-ц. Такой код может обнаруживать все 1-кр.ош. Выберем в кач-ве разреш. слова с dmin=3: 000,111.Этим словам соотв-вуют запрещ.слова: для 000: 001, 010, 100; для 111: 110, 101, 011.При этом любая 1-кр.ош. переводит соотв-щее разреш. слово в подмн-во принадлеж-их ему запрещ. слов. Это позволяет исправить все 1-кр.ош.
dmin ≥ (r+1) – для кода, только обнаруж. ош-ки r-кратности.
dmin для кода,исправл.ош-ки кр-ти S: dmin ≥ (2S+1).
Если треб-тся обнаруживать ош-ки кратности r>S и исправлять ош-ки кр-ти S: dmin≥r+S+1.
Понятие вектора ошибки. Виды ошибок. Вероятность r-кратной ошибки в n-разрядном слове.
Вектор ош. – двоичн. кодовое слово такой же длины как исходное, содержащее ед-цы в тех разрядах, где произошло искажение содержимого код. слова. (код. слово и вектор ош. - абстракция). Воздействие помехи на слово заменяется слож-ем по mod2 исходн. слова с вектором ош.
Ошибки различают на некорректируемые и корректируемые.
Некорректир – при которых изменение содержимого в каком-то разряде слова не влияет на искажение содержимого в других словах.
При корректир – изменение содержимого под влиянием помех влечёт искажение содержимого некоторых других разрядах.
Различают ош. разной кратности:
1)однократные,
2)двукратные,
3)r-кратные (одновременное искажение содержимого в r- разрядах).
Однократная ошибка вызывает искажение содержимого только 1 разряда слова и т.д.
Вероятность r-кратной ошибки в n-разрядном слове:
-кол-во таких ошибок
Вероятность такого события – вероятность сложного события и определяется произведение следующих множителей: вероятности, что искажение произойдет в этом разряде p, т.к. таких разрядов r и события независимые, то - pr , вероятности, что в остальных (n-r) разрядах искажения не будет определяется как (1-p)(n-r) , умноженных на количество возможных r-кратных ошибок. Т.о.
P= 
Формулы для определения числа избыточных разрядов и границы Хэмминга для оптимальных корректирующих кодов; их суть и связь, примеры использования.
Пусть имеем n-разр. слова, требуется исправлять ошибкки вплоть до кратности S. Определим, какое мн-во разреш-х код. слов можно выделить на мн-ве всех n-разр-х слов. Для каждой исправляемой ош-ки. соотв-щее ей запрещ. код. слово. Поэтому «вокруг» каждого разреш. слова должны сгруппироваться те запрещ. слова, ош-ки кот-х подлежат исправлению. Поэтому кол-во запрещ. слов. не <, чем число исправл-ых ошибок.
2k-1>=Q – определяется число информационных разрядов; 2n-k-1>=n – определяется число разрядов помехоустойчивого слова; n-k=m - определяется число избыточных разрядов; 
– определяется граница Хемминга. Дополнительных разрядов в кодовом слове должно быть столько, чтобы породить нужное число запрещенных слов или классов смежности, а именно 2n-k-1. Число классов смежности должно быть не меньше, чем число исправляемых ошибок, поэтому – 2n-k-1>=n
Пример: Пусть для построения кода, корректирующего все однократные ошибки, используются однобайтовые слова. Требуется определить максимальное число разрешенных слов, выбираемых из всего множества однобайтовых слов.
Число однократных ошибок 
,т.е. 
.
Максимальное число разрешенных слов
,т.е.
Дата добавления: 2018-05-12; просмотров: 439; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!