Минимальное кодовое расстояние в С k x m должно быть не менее d min – 2
Таким образом порождающая матрица имеет вид
1000 ..… 0 e11 e12 ….. e k
M n x m = 0100 ..… 0 e21 e22 ….. e k
………………………………
0000 ..… 1 em1 em2 ….. e mk
Пример : Используя для расчета k границу Хэмминга построить порождающую матрицу для кода способного исправлять одиночную ошибку ( t = 1 ) при передаче N =16 сообщений для N=16 m = 4 N = 2m (d min -1 )/ 2
граница Хэмминга k >= log 2 ( 1 + ∑ c in )
i=1 для обнаружения t ошибок d min >= t + 1
для исправления t ошибок d min >= 2 t + 1
У нас d min >= 2*1 +1 = 3
1
k >= log 2 ( 1 + ∑ c 1n ) , k >= log 2 ( 1 + n ) , k = 3
1
1000 101 1000 111
M 7,4 = 0100 011 или 0100 110 или и т.д.
0010 110 0010 011
0001 111 0001 101
Алгоритм образования значений контрольных разрядов кодовой комбинации по информационной части с помощью матрицы M n x m выглядит так :
e1 = e11 а1 + e21 а2 + …..+ e m1 аm
e2 = e12 а1 + e22 а2 + …..+ e m2 аm
………………………………………
ek = e1k а1 + e2k а2 + …..+ e mk аm
Гораздо удобнее проверочные уравнения выполнить с помощью матрицы , состоящей из k строк и m столбцов. Получим ее : сначала строится единичная матрица Е k,k . К ней приписывается D m,k , содержащая m столбцов и k строк, причем каждая ее строка соответствует столбцу контрольных разрядов подматрицы С k,m , порождающей матрицы, другими словами D k,m является транспонированной по отношению к С k,m.
e11 e21 ….. em1 100 ……0
H n x k = [D m,k ; Ek ] e12 e22 ….. em2 010 …….0
………………………………
e1k e2k ….. emk 000 ..… 1
С помощью этой матрицы операция кодирования осуществляется очень просто : позиции занимаемые единицами в i – ой строке подматрицы D m,k определяют те информационные разряды, которые должны участвовать в формировании контрольного разряда
Пример : Построить проверочную матрицу H кода 7,4 , порождающая матрица которого имеет вид :
1000 111 1110 1110100
M 7,4 = 0100 110 D 4,3 = 1101 H 7,3 = 1101010
0010 101 1011 1011001
0001 011
Для расчета контрольных разрядов при кодировании по этой матрице получают следующие контрольные соотношения
e1 = a1 + a2 + a3
e2 = a1 + a2 + a4
e3 = a1 + a3 + a4
Закодируем 1 0 1 0 0 1 0
a1 a2 a3 a4 e1 e2 e3
На основании матричного представления кодов можно сделать следующие выводы :
1) С помощью порождающей матрицы M m x n можно представить весь набор кодовых комбинаций в удобной и компактной форме и довольно просто провести операцию кодирования.
2) Проверочную матрицу H m x k обычно используют при построении кодирующих и декодирующих устройств, т.к. она определяет алгоритм нахождения проверочных разрядов по информационным значениям. Кроме того данная очень удобна для указания места отсечки в кодовой комбинации
Метод исправления ошибок в линейных кодах. Понятие синдрома.
Обычно при декодировании информации используются проверочные соотношения полученные по проверочной матрице H m x k . При этом вычисляется синдром (контрольное число). Синдром рассчитывается как сумма по модулю 2 принятых контрольных разрядов и контрольных разрядов, вычисленных по принятым информационным. Характерной особенностью синдрома является то, что он независим от передаваемой кодовой комбинации, а зависит только от характера ошибок.
Пример : Задана проверочная матрицаH 7 x 3
0 1 1 1 1 0 0 S1 = e1 + e1 /
H 7,3 = 1 0 1 1 0 1 0 S2 = e2 + e2 /
1 1 0 1 0 0 1 S2 = e3 + e3 /
a1 a2 a3 a4 e1 e2 e3
e1 / - контрольный разряд, вычисленный по принятым информационным
e1 / = a2 + a3 + a4
e2 / = a1 + a3 + a4
e3 / = a1 + a2 + a4
Возьмем А = 1 0 1 1 0 1 0
a1 a2 a3 a4 e1 e2 e3
Пришедшее число 1 0 1 1 1 1 0
a1 a2 a3 a4 e1 e2 e3
S1 = 1+0 = 1 0111 100
S2 = 1+1 = 0 1011 010
S3 = 0+0 = 0 S = 1 0 0 1101 001
(в этом разряде ошибка)
Покажем, что синдром не зависит от вида передаваемой информации, а зависит только от возникающих ошибок. Предположим произошла ошибка в информационном разряде a1.
Составим последовательность ошибок 1000 000
S1 = 0+0 = 0
S2 = 0+1 = 1
S3 = 0+1 = 1
Количество разрядов синдрома для обнаружения одиночной ошибки определяется следующим выражением :
2k >= n-1
2k+1 >= n
k >= Cn1
Для исправления одиночных и двоичных ошибок 2k + 1>= Cn1 + Cn2
Для всех разрядов 2k + 1>= Cn1 + Cn2 + …. + Cne
Код с простым повторением
В этом коде передаваемая информация повторяется дважды. При декодировании производится поразрядное сравнение и если получено отличие в разрядах, то фиксируется наличие ошибки.
Данный код обнаруживает все ошибки за исключением искажения в обоих одинаковых разрядах в первой и второй переданной комбинациях.
Инверсный код
Одной из разновидностей кода с простым повторением является инверсный код. В этом коде, если передаваемая информационная часть содержит четное число единиц
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.