14. Варианты разбиения множества n-разрядных кодовых слов при построении корректирующих кодов; способы кодирования и декодирования.

1-й способ: разбиение всех запрещенных слов на непересекающиеся подмножества по принципу принадлежности (близости) запрещенного слова к разрешенному кодовому слову. При этом "вокруг" каждого разрешенного кодового слова группируются такие запрещенные слова, которые "ближе" к нему, чем к другим разрешенным словам. В этом случае в качестве разрешенных кодовых слов следует выбирать такие, которые составляют множество элементов, удаленных друг от друга на расстояние не меньше некоторой величины (называемой минимальным хэмминговым расстоянием).

При таком способе разбиения дешифратор выносит решение в пользу того разрешенного слова, расстояние от которого до принятого слова меньше, чем до других разрешенных слов. Количество непересекающихся подмножеств запрещенных кодовых слов при этом равно числу разрешенных слов 2^k.

2 -й способ: разбиение по принципу принадлежности запрещенного кодового слова к вектору ошибки или к классу смежности. При таком разбиении декодер опознает не переданное ему слово, а вектор ошибки, которой оно оказалось поражено. Для этого декодер, учитывая содержимое избыточных и информационных разрядов, проверяет принятое слово на соответствие данному алгоритму кодирования и в результате вычисляет опознаватель (синдром) ошибки, который указывает на принадлежность принятого слова к одному из непересекающихся подмножеств запрещенных слов (классов смежности), "порожденных" определенным вектором ошибки. В такой системе кодер должен по определенным правилам кодирования определять содержимое избыточных разрядов на основе известного содержимого информационных разрядов. Эти правила или алгоритм кодирования представляют собой систему уравнений, в которых данными (известными величинами) являются значения информационных разрядов. Для определения содержимого каждого избыточного разряда применяется свое уравнение. Дешифратор проверяет на истинность каждое из этих уравнений, проверка дает либо "0", либо "1". Проверки всех уравнений дают множество нулей и единиц, называемое опознавателем ошибки. Если опознаватель состоит только из одних нулей, декодер делает вывод об отсутствии ошибки, иначе, по виду ненулевого опознавателя, декодер может определить тип ошибки, так как опознаватель указывает на принадлежность принятого слова подмножеству запрещенных слов, порожденных данным вектором ошибки.

15. Понятия минимального Хэммингова расстояния и его величина для кодов, обнаруживающих и исправляющих ошибки. Примеры.

Для определения степени различия м/у кодовыми словами вводится спец. метрика – кодовое или Хэммингово расст-е. Расст-е м/у 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.