Для исправления ошибок кратности t кодовое расстояние должно удовлетворять условию: .

Для исправления ошибки кратности s кодовое расстояние должно быть:

.

Если код должен исправлять ошибки кратности t и обнаруживать ошибки кратности s, то кодовое расстояние должно быть не менее

Помехоустойчивые коды делятся на два больших класса:

1. Блоковые коды;

2. Непрерывные коды.

Для блоковых кодов к каждой исходной комбинации добавляется блок избыточных символов и получается новая комбинация (рисунок 4.2).

Рисунок 4.2 – Построение блокового кода

Различают разделимые и неразделимые блоковые коды. В разделимых блоковых кодах k символов являются информативными, а r - проверочными.

Такие коды обозначают как (n,k) – коды.

Для неразделимых кодов разделить символы на информативные и проверочные невозможно (см. далее корреляционный код).

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

Вопрос 29.  Вероятность ошибочного приема кодовой информации для простого двоичного кода и для кода с исправлением ошибок кратности t. 

Для двоичного симметричного канала передачи вероятность ошибочного приема любых l символов в n-элементной кодовой комбинации подчиняется биномиальному закону распределения

P_n(l)=C_n^lp^l(1-p)^n-l.

Неправильный прием одного, двух, и т.д. элементов из n-элементной кодовой комбинации обозначают термином «одиночная», «двойная» и т. д. ошибка соответственно. Или говорят, что произошла ошибка кратности l.

Если код исправляет ошибки кратности t, то вероятность ошибочного приема кодовой комбинации равна

. (4.4)

Пусть исправляется ошибка кратности t=1. Тогда из (4.4) для рассмотренного выше примера (где n=8) получим:

Р_К=8*10^-3 – 8*10^-3*0.999⁷)≈5.6*10^-5.

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

Вопрос 30. Простейшие избыточные коды.

ПРОСТЕЙШИЕ ИЗБЫТОЧНЫЕ КОДЫ

Код с четным числом единиц. Код с четным числом единиц образуется из исходного k-элементного кода добавлением еще одного элемента, нуля или единицы, таким образом, чтобы количество единиц в новой кодовой комбинации было четным. Для определения дополнительного элемента все элементы исходной кодовой комбинации складывают по модулю 2:

0 1 1 1 0 1 1 0 = 1,

0 0 1 1 0 1 1 0 = 0.

Таким образом, число элементов в новой кодовой комбинации n=k+r=k+1. Избыточность кода с четным числом единиц

. (4.5)

Этот код имеет кодовое расстояние d=2 и обнаруживает все нечетные ошибки.

Корреляционный код

При построении корреляционного кода каждый элемент исходного кода преобразуется в 2 элемента:

1 à 10,

0 à 01.

Таким образом, корреляционный код относится к непрерывным кодам.

Если исходная комбинация содержит k элементов, то новая кодовая комбинация – n=2k. Избыточность корреляционного кода R=0,5 .

---

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

Р_НО=р². В корреляционном коде в линию связи всегда передается одинаковое число 0 и 1, что обеспечивает эффективное использование ее пропускной способности.

Вопрос 31. Групповой код Хемминга. Принципы построения. Синдром ошибки. 

КОДЫ С ОБНАРУЖЕНИЕМ И ИСПРАВЛЕНИЕМ ОШИБОК.

КОД ХЕММИНГА

Код Хемминга относится к блоковым кодам. Наиболее простой код, исправляющий ошибки кратности t=1, имеет кодовое расстояние d=3.

Принцип построения:

1) На передающей стороне к k информационным символам добавляется r проверочных символов. Значения проверочных символов (0 или 1) определяются путем проверок на четность. В проверку на четность включают определенные элементы кодовых комбинаций, образующие проверочную группу. Сформированный n-разрядный код, состоящий из k информационных и r проверочных элементов, передается в линию связи.

2) На приемной стороне в тех же проверочных группах производится r проверок на четность.

3) Проверочные группы строятся таким образом, чтобы записи результатов каждой проверки в двоичной форме давало бы r-разрядное двоичное число , указывающее номер разряда (в исчислении с основанием 10) искаженного элемента. Это выражение называют синдромом ошибки.

Для того чтобы обнаружить и исправить все ошибки кратности 1, число проверочных символов выбирается из соотношения . Добавление слагаемого +1 соответствует случаю отсутствия ошибок.

Число элементов помехоустойчивой кодовой комбинации определяется из решения уравнения относительно n:

. (4.6)

Изначально известно число k. Определив n из уравнения (4.6), получим число проверочных разрядов r в новых кодовых комбинациях (таблица 4.1).

Таблица 4.1 – Соотношение числа информационных и проверочных разрядов

k	2	3	4	5	6	7	8	9	10	11	12
n	5	6	7	9	10	11	12	13	14	15	17
r	3	3	3	4	4	4	4	4	4	4	5

Вопрос 32. Определение числа проверочных элементов. 

Выбор значений и позиций проверочных элементов

Если ошибок нет, то синдром ошибки имеет значение 00…00.

При наличии ошибки двоичный код синдрома ошибки должен указать номер разряда кодовой комбинации (в исчислении с основанием 10), в котором произошло искажение элемента.

Единица в первом разряде синдрома ошибки появляется при искажении любого нечетного разряда кодовой комбинации.

Таким образом, в первую проверку должны войти все нечетные элементы принятой кодовой комбинации

---

(4.7)

То есть в первую проверку должны входить все элементы кодовой комбинации, в первом (младшем) разряде содержится 1. Если , то один из элементов искажен.

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

(4.8)

Если S₂=1, то один из элементов искажен:

Третья проверочная группа содержит элементы, принимающие значение 1 в третьем разряде новой кодовой комбинации:

(4.9)

Четвертая проверочная группа содержит элементы, принимающие значение 1 в четвертом разряде новой кодовой комбинации:

(4.10)

Проверочные элементы каждой кодовой комбинации должны входить только в одну проверку. Таким образом, проверочными должны быть символы, расположенные в 1-м, 2-м, 4-м, 8-м и т. д. (16-м, 32-м,…) разрядах полученной кодовой комбинации.

Обозначим проверочные символы как . Тогда

; ; ; . (4.11)

Пример:

1 0 0 0 0 1 1 – исходная кодовая комбинация (младший разряд слева), k=7.

k₁k₂k₃k₄k₅k₆k₇

По таблице 4.1 найдем число проверочных символов r=4. Помехоустойчивая кодовая комбинация должна содержать n=k+r =11 элементов (разрядов)

k₁ k₂ k₃ k₄ k₅ k₆ k₇

а₁ а₂ а₃ а₄ а₅ а₆ а₇ а₈ а₉ а₁₀ а₁₁ (а₁ – младший разряд).

b₁ b₂ b₃ b₄

Выполнив проверку на четность по описанным выше правилам, определим значения проверочных элементов:

;

;

;

.

Получится новая кодовая комбинация 01100000011, содержащая информационные биты и проверочные биты.

Пусть принят код 01101000011, то есть произошла ошибка в 5-м разряде.

Проверочные группы на приемной стороне:

;

;

;

;

Таким образом, синдром ошибки

, то есть, выявлена ошибка в бите .

Для ее исправления надо выполнить операцию суммирования а₅ с 1 по модулю 2: а₅= а₅1.

Вопрос 33. Определение проверочных элементов, входящих в каждую группу.

ИСПРАВЛЯЮЩАЯ СПОСОБНОСТЬ КОДА ХЕММИНГА

Если имеется n символов, то вероятность правильного приема этих символов равна , где р – вероятность искажения одного символа.

Вероятность появления однократной ошибки .

Вероятность ошибочного приема кодовой комбинации:

;

;

.

Для исправления ошибки кратности больше 1 необходимо выполнение условия , где t – кратность ошибки.

Эти выражения справедливы при вероятности

---

Смотрите также файлы

• Навч.посібник Акушерство, гінекологія та штучне осіменіння с.г. тварин, Харута, 2013.pdf

• Ветеринарне акушерство, Яблонський, 2006.pdf

• МЕДИКО-тактическая характеристика очагов.docx

• Этика ДО Экзамен Ответы.docx

• 1.3 Формы общественной организации производсива.docx