Алгоритмы кодирования и декодирования для линейных, циклических и БЧХ кодов. v1.0 (1127210)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Алгоритмы кодирования/декодирования для линейных,циклических и БЧХ кодовВезде в тексте все вычисления проводятся в двоичной арифметике.Рассмотрим задачу передачи потока битовой информации по каналу с шумом с возможностьюавтоматического исправления ошибок, допущенных при передаче. При блоковом кодировании входящий поток информации разбивается на блоки фиксированной длины k.

Обозначим один такойблок через u ∈ {0, 1}k . Предполагается, что во входном потоке данных, вообще говоря, нет избыточности. Поэтому для реализации схемы, способной исправлять ошибки, необходимо закодироватьблок u в некоторое кодовое слово большей длины путем добавления избыточности в передаваемыеданные. Обозначим кодовое слово через v ∈ {0, 1}n , n > k, а через m = n − k – количество требуемых дополнительных бит. Для кодирования всевозможных блоков u необходимо использовать2k кодовых слов длины n.

Определим минимальное расстояние кода d как минимальное хэммингово расстояние для всех различных пар кодовых слов. Назовём множество 2k кодовых слов длиныn с минимальным расстоянием d (n, k, d)-блоковым кодом, а величину r = k/n – скоростью кода.При передаче по каналу с шумом кодовое слово v превращается в принятое слово w = v + e, гдеe ∈ {0, 1}n – вектор ошибок (ei = 1, если в i-ом бите произошла ошибка). Далее алгоритм декодирования пытается восстановить переданное слово v путем поиска среди всевозможных кодовых словближайшего к w. Обозначим результат работы алгоритма декодирования через v̂.

На последнемэтапе декодированное слово v̂ переводится в декодированное слово исходного сообщения û. Очевидно, что (n, k, d)-блоковый код способен обнаруживать до d − 1 ошибки и исправлять до [(d − 1)/2]ошибок.Линейные кодыМножество {0, 1}n с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем из двух элементов {0, 1}. Блоковый (n, k, d)-код C называется линейным,если множество его кодовых слов образует линейное подпространство размерности k общего линейного пространства {0, 1}n .

Таким образом, для линейного кода произвольная линейная комбинациякодовых слов является кодовым словом. Минимальное кодовое расстояние d для линейного кодаопределяется как минимальный хэммингов вес (количество ненулевых бит) среди ненулевых кодовых слов. Пусть g 0 , g 1 , . . . , g k−1 ∈ {0, 1}n – базис C. Тогда v ∈ C может быть представлено какPk−1v = i=0 ui g i , ui ∈ {0, 1} или, эквивалентно, v = Gu, где G = [g 0 |g 1 | . .

. |g k−1 ] ∈ {0, 1}n×k – порождающая матрица кода. Матрица G определена с точностью до эквивалентных преобразованийстолбцов.Кодирование. Несистематическое кодирование линейного кода, заданного своей порождающей матрицей G, может быть осуществлено как v = Gu, где u ∈ {0, 1}k – блок исходного сообщения.Очевидно, что с помощью эквивалентных преобразований столбцов матрица G может быть приведена к виду, в котором некоторые k строк образуют единичную подматрицу. Пусть, не ограничиваяIkобщности, единичная подматрица образуется в первых k строках матрицы G, т.е.

G =, где Ik –Pединичная матрица размера k×k, а P ∈ {0, 1}m×k . Тогда кодирование по правилу v = Gu будетсистематическим, при котором первые k бит кодового слова v являются битами исходного сообщения u. При использовании систематического кодирования этап преобразования из декодированногокодового слова v̂ в декодированное сообщение û становится тривиальным.Линейное пространство {0, 1}n может быть разложено в прямую сумму линейных подпространств C и C ⊥ , где C ⊥ – ортогональное подпространство для C, dim C ⊥ = m. Пусть1h0 , . . . , hm−1 ∈ {0, 1}m – базис C ⊥ . Составим матрицу T h0 hT1 H =  .  ∈ {0, 1}m×n . .. hTm−1Очевидно, что hTj g i = 0 ∀i, j. Следовательно, для любого кодового слова v ∈ C выполнено Hv = 0.МатрицаH называется проверочной матрицей кода.

Пусть порождающая матрица G имеет вид Ik. Тогда проверочная матрица H может быть построена как H = P Im ∈ {0, 1}m×n , где Im –Pединичная матрица размера m×m. Действительно, в этом случае Hv = HGu = (P + P )u = 0.Пример 1. Линейный блоковый (6,3)-код задан порождающей матрицей0 0 11 0 11 0 0.G=1 1 11 1 00 1 1Требуется для данного кода осуществить несистематическое и систематическое кодирование векторов u1 = [0 1 1]T и u2 = [1 0 1]T , построить проверочную матрицу кода H, а также определитьминимальное кодовое расстояние d.Несистематическое кодирование находим непосредственно:1 10 0 11 01 0 11 0 00 1[v 1 , v 2 ] =  [u1 , u2 ] = 0 0 .1 1 11 11 1 00 10 1 1Для построения систематического кодирования с помощью эквивалентных преобразований столбцов выделим в матрице G единичную подматрицу размера 3×3 (над стрелками указано проводимоепреобразование над столбцами):0 0 10 0 11 0 11 0 11 0 0 1←1+2 1 0 0 −−−−−→ 0 1 1 .1 1 11 1 00 1 01 1 10 1 1В последней матрице в строках (3, 5, 1) стоит единичная подматрица.

В результате систематическоекодирование u1 , u2 , при котором биты 1, 2, 3 исходного сообщения переходят, соответственно, в биты3, 5, 1 кодового слова, вычисляется следующим образом0 0 11 11 0 11 01 0 0 [u1 , u2 ] = 0 1 .[v 1 , v 2 ] = (1)0 1 10 10 1 01 01 1 10 0С учетом выделенной единичной подматрицы в порождающей матрице G, нетрудно найти проверочную матрицу кода H.

Для этого формируем матрицу P из строк G, отличных от строк с1 0 1единичной подматрицей, т.е. P = 0 1 1. Далее1 1 1в 3-ом, 5-ом и 1-ом cтолбце H, а во 2-й, 4-ый и 6-ой1 1 1H = 1 0 01 0 1нужно разместить столбцы P , соответственно,столбец H поставить единичную подматрицу:0 0 01 1 0 .0 1 1Проверим, что полученная матрица действительно является проверочной матрицей кода. Для этоговычислим HG:0 0 1 1 0 1 0 0 01 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 = 0 0 0 .0001 0 1 0 1 1 0 1 01 1 1Проверим также, что в результате систематического кодирования (1) были действительно найденыкодовые слова:1 1 1 0 0 01 1 1 0 0 0 0 1 H[v 1 , v 2 ] = 1 0 0 1 1 0 0 1 = 0 0 .001 0 1 0 1 1 1 00 0Найдем теперь минимальное кодовое расстояние d.

Для этого построимкодовых слов и найдем для них минимальный ненулевой хэммингов вес:0 10 0 11 0 1  0 11 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 = 0 0[v 1 , . . . , v 8 ] = G[u1 , . . . , u8 ] = 0 10 1 10 00 1 0 0 1 0 1 0 1 0 10 11 1 1матрицу всех 23 = 8000111110010011110101011011001101.100Отсюда получаем, что d = 3.

Следовательно, рассмотренный код способен исправить одну ошибкуи обнаружить две ошибки.Декодирование. Назовём синдромом принятого сообщения w вектор s = Hw, где H – проверочная матрица кода. С учётом представления w = v + e, получаем s = Hw = H(v + e) =Hv + He = He. Очевидно, что синдром является нулевым вектором тогда и только тогда, когдапринятое сообщение является кодовым словом.

Вектор ошибок удовлетворяет системе линейныхуравнений He = s. Матрица данной системы имеет размер m×n. Следовательно, все решения данной СЛАУ описываются как e = ê + Gu, где ê – произвольное частное решение системы, а Gu –решение однородной системы He = 0, где u – произвольный вектор длины k.

Таким образом, получаем 2k различных решений для вектора ошибок e. Среди них решение с наименьшим хэмминговымвесом дает искомый вектор ошибок.Пример 2. Рассмотрим линейный код из примера 1. Пусть исходный вектор u = [0 1 1]T .Систематическое кодирование для него было получено раньше: v = [1 1 0 0 1 0]T . Пусть при передачепроисходит ошибка во втором бите, т.е. принятый вектор w = [1 0 0 0 1 0]T . Для декодирования wнайдём его синдром 1 0  1 1 1 0 0 0 10s = Hw = 1 0 0 1 1 0  = 0 .01 0 1 0 1 1 010Далее необходимо найти все решения системы He = s.

Частное решение этой системы легко найтис учётом того, что в столбцах 2, 4, 6 проверочной матрицы H стоит единичная подматрица. Пустьê1 = ê3 = ê5 = 0. Тогда ê2 = s1 , ê4 = s2 , ê6 = s3 , т.е. ê = [0 1 0 0 0 0]T . Решение однородной системыуже было найдено раньше на этапе вычисления кодового расстояния d:0 1 0 1 0 1 0 10 1 0 1 1 0 1 00 0 0 0 1 1 1 1G[u1 , u2 , . .

. , u8 ] = 0 1 1 0 1 0 0 10 0 1 1 1 1 0 00 1 1 0 0 1 1 0Таким образом, все 8 решений системы010000He = s могут быть записаны как1 0 1 0 1 0 10 1 0 0 1 0 10 0 0 1 1 1 11 1 0 1 0 0 10 1 1 1 1 0 01 1 0 0 1 1 0Выбирая среди них решение с наименьшим весом, находим e = [0 1 0 0 0 0]T , т.е. v̂ = w + e =[1 1 0 0 1 0]T .Циклические кодыЛинейный блоковый (n, k, d)-код называется циклическим, если любой циклический сдвиг кодового слова является кодовым словом. Поставим в соответствие произвольному вектору v ={v0 , v1 , . .

. , vn−2 , vn−1 } ∈ {0, 1}n полином вида v(x) = v0 + v1 x + · · · + vn−2 xn−2 + vn−1 xn−1 . Тогда можно показать, что для (n, k, d)-линейного циклического блокового кода найдется полиномg(x) степени m = n − k такой, что1. Все кодовые слова v(x) могут быть представлены как g(x)q(x), где q(x) – некоторый полиномстепени не выше, чем k − 1;2.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов учебной работы