close

Вход

Забыли?

вход по аккаунту

?

27

код для вставкиСкачать
Вопрос №1. Механизм кодирования и синхронного декодирования.
Предположим, что имеет место некоторое информационное сообщение, состоящее из символовa_1, a_2, ..., a_k.
Установить (n, k), где n - общее число символов;
k - количество информационных символов.
Значит, линейным кодом заданного информационного сообщения будет некоторая кодовая комбинация, состоящая из некоторых информационных символов a_1, a_2, ..., a_k и проверочных символов b_1, b_2, ..., b_r, где r=n-k.
В этой линейной комбинации информационная часть полностью повторяет заданное информационное сообщение, а проверочные символы формируются путем сложения по модулю два определенных информационных символов.
В общем случае, правило формирования проверочных символов, имеет вид:
b_i= β_i1*a_1⊕β_i2*a_2⊕...⊕β_ik*a_k, i=(1, r) ̅.
Это правило кодирования информационных линейных помехоустойчивых кодов.
β_ij={█(1, если a_j учавствует в формировании b_i@0, иначе)┤
j=(1, k) ̅.
Механизм декодирования линейных помехоустойчивых кодов должен позволять обнаруживать ошибки в принятой комбинации и исправлять их с заданной кратностью. Этот механизм реализуется на понятии "синдром" или вектор ошибок.
Синдром - это специальная совокупность символов, сформированная по правилу: берутся принятые проверочные символы b ̂_1, ..., b ̂_r складываются по модулю два с вычисленными символами b ́_1, ..., b ́_r и получаем значение синдрома C_1, ..., C_r. Размерность комбинации r.
При этом вычисленные символы b ́_1, ..., b ́_rопределяются по тому же правилу кодирования, но с использованием принятых информационных символов, т.е.:
b ́_i= β_i1*a ̂_1⊕β_i2*a ̂_2⊕...⊕β_ik*a ̂_k.
Эти правила составляют механизм декодирования. При этом можно показать, что если ошибки в принятой кодовой комбинации отсутствуют, то все символы синдрома равны 0. То есть в качестве признака обнаружения ошибок используется ненулевое значение синдрома.
Для исправления ошибок коэффициенты β_ij в механизме кодирования задаются таким образом, что конкретные значение синдрома указывает на конкретный символ кодовой комбинации, в котором произошла ошибка, т.е. значение синдрома позволяет исправить ошибки в принятой кодовой комбинации. Таким образом, основная проблема построения линейного помехоустойчивого кода состоит в выборе коэффициентов β_ij именно так, что бы синдром позволял исправить ошибки.
Рассмотрим эту процедуру на конкретном примере.
Пусть необходимо сформировать линейных помехоустойчивый код, используя семи разрядную линейную комбинации, способный исправлять одиночные ошибкиn=7, t=1, d_min=3.
Использую известные границы для необходимых и достаточных символов вычислим r_x по Хеммингу:
r_x = 〖log〗_2 ∑_(i=0)^((d_min-1)/2)▒C_n^i =0 - верхняя граница.
r_(В-Г)=3 - нижняя граница, тогда получим (7,4) код, n=7, n-r=k=4.
С такими условиями код будет делать то, что от него требуется.
Кодовая комбинация в нашем (7,4) коде будет иметь вид:
a_1 a_2 a_3 a_4 b_1 b_2 b_3.
Для этой кодовой комбинации напишем общее правило формирования проверочных символов:
{█(b_1= β_11*a_1⊕β_12*a_2⊕β_13*a_3⊕β_14*a_4@b_2= β_21*a_1⊕β_22*a_2⊕β_23*a_3⊕β_24*a_4@b_3= β_31*a_1⊕β_32*a_2⊕β_33*a_3⊕β_34*a_4 )┤.
Известно, что нулевой синдром соответствует отсутствию ошибок, тогда произвольным образом установим соотношения между конкретным синдромом и конкретным символом в кодовой комбинации, в которой происходит ошибка, причем для нашего кода синдром является трех разрядной комбинацией.
Синдром:
100 → ошибка в b ̂_1;
010 → ошибка в b ̂_2;
001 → ошибка в b ̂_3;
011 → ошибка в a ̂_1;
101 → ошибка в a ̂_2;
110 → ошибка в a ̂_3;
111 → ошибка вa ̂_4.
Анализируя, заданное значение синдрома, общее правило его получения и конкретные правила формирования проверочных символов для нашего кода, можно заметить, что коэффициенты β, связанные с конкретным информационным символом, должны соответствовать синдрому ошибки в этом символе.
Значение коэффициентов β определяется введенными нами значениями синдрома для соответствующей кодовой комбинации.
Тогда правило формирования символов приобретает конкретный вид линейных операций:
{█(b_1= a_2⊕a_3⊕a_4@b_2= a_1⊕a_3⊕a_4@b_3= a_1⊕a_2⊕a_4 )┤
В соответствии с этими правилами можно проверить будет ли работать наш код.
a ̂_1 a ̂_2 a ̂_3 a ̂_4 b ̂_1 b ̂_2 b ̂_3 = a_1 a_2 a_3 a_4 b_1 b_2 b_3 (C_1 C_2 C_3=000).
Проверим: 1101001→1 ̂1 ̂0 ̂1 ̂0 ̂0 ̂1 ̂
Вычисленные значения:
{█(b_1= a_2⊕a_3⊕a_4=1⊕0⊕1=0@b_2= a_1⊕a_3⊕a_4=1⊕0⊕1=0@b_3= a_1⊕a_2⊕a_4=1⊕1⊕1=1)┤
b ̂_1 b ̂_2 b ̂_3⊕b_1 b_2 b_3=C_1 C_2 C_3;
001⊕001=000.
Пусть в третьем символе ошибка: 1101001→1 ̂1 ̂1 ̂1 ̂0 ̂0 ̂1 ̂, тогда001⊕111=110 → из таблицы следует, что это ошибка в a ̂_3.
Сделаем ошибку в проверочном символе: 1101001→1 ̂1 ̂0 ̂1 ̂1 ̂0 ̂1 ̂, тогда 101⊕001=100 → из таблицы следует, что это ошибка в b ̂_1.
На практике имеет место линейные коды, у которых десятичное значение синдрома указывает непосредственно номер позиции в кодовой комбинации, в которой произошла ошибка. Это упрощает процедуру исправления и устраняет необходимость передачи в декодер соответствующей таблицы синдромов.
Такие линейные кодеки часто изображают схематически в следующем виде:
Документ
Категория
Без категории
Просмотров
9
Размер файла
22 Кб
Теги
1/--страниц
Пожаловаться на содержимое документа