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

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

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

Курс: Прикладная алгебра, 3-й потокАлгоритмы кодирования/декодирования для линейных,циклических и БЧХ кодовВ тексте все вычисления проводятся в двоичной арифметике.Задача помехоустойчивого кодированияРассмотрим задачу передачи потока битовой информации по каналу с шумом с возможностью автоматическогоисправления ошибок, допущенных при передаче. При блоковом кодировании входящий поток информации разбивается на непересекающиеся блоки фиксированной длины k, каждый из которых кодируется и декодируетсянезависимо1 . Обозначим один такой блок через u ∈ {0, 1}k .

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

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

Таким образом, при передаче не происходит добавлений или стираний битов, а ошибки могут возникать в произвольных битах3 . После получения w алгоритм декодирования пытаетсявосстановить переданное слово v путем поиска среди всевозможных кодовых слов ближайшего к w в метрикеХэмминга. Обозначим результат работы алгоритма декодирования через v̂. На последнем этапе декодированноеслово v̂ переводится в декодированное слово исходного сообщения û.Определим минимальное расстояние блокового кода d как минимальное хэммингово расстояние для всехпар различных кодовых слов.

Очевидно, что код с расстоянием d способен обнаруживать до d − 1 ошибки4 иисправлять до [(d − 1)/2] ошибок.В общем случае для задания (n, k)-блокового кода необходимо использовать таблицу всех кодовых слов размера 2k ×n, а на этапе декодирования необходимо перебирать все 2k кодовых слов для поиска ближайшего кпринятому w. В результате на практике использование произвольного (n, k)-блокового кода возможно толькопри небольших значениях n и k.

Далее в тексте будет рассмотрен ряд дополнительных ограничений на множество кодовых слов блокового кода, которые позволят перейти от экспоненциальных требований по памяти дляхранения кода и по сложности алгоритмов кодирования/декодирования к линейным по n и k.Линейные кодыМножество {0, 1}n с операциями суммы и произведения по модулю 2 образует линейное пространство над конечным полем из двух элементов {0, 1}. Блоковый (n, k)-код C называется линейным, если множество его кодовыхслов образует линейное подпространство размерности k общего линейного пространства {0, 1}n . Таким образом,для линейного кода произвольная линейная комбинация кодовых слов является кодовым словом.

Для линейногокода минимальное расстояние d может быть вычислено более эффективно, чем для произвольного блоковогокода: это расстояние определяется как минимальный хэммингов вес (количество ненулевых бит) среди всех1 Альтернативой блоковому кодированию является свёрточное кодирование, при котором вычисляется свёртка входящего потокаинформации с некоторой фиксированной последовательностью, т.е. результат кодирования зависит не только от текущего блокадлины k, но и от некоторого количества предыдущих блоков. Одним из наиболее успешных семейств свёрточных кодов являютсят.н. турбо-коды.2 Например, по сети передаётся zip-архив.3 Альтернативой здесь является случай возникновения пакетов ошибок, связанных, например, с коммуникационными помехами.4 Здесь речь идёт о гарантированном обнаружении произвольных d − 1 ошибок.

В общем случае (n, k)-блоковый код способенобнаружить 2n − 2k векторов ошибок, т.е. таких векторов ошибок, которые не переводят одно кодовое слово в другое.ненулевых кодовых слов5 . Код C является линейным пространством размерности k, следовательно, Pу него суk−1ществует базис из k векторов g 0 , g 1 , . . . , g k−1 ∈ {0, 1}n . Тогда v ∈ C может быть представлен как v = i=0 ui g i ,ui ∈ {0, 1} или, эквивалентно, v = Gu, где G = [g 0 |g 1 | . . .

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

Однако, на практике оказывается удобным т.н. систематическое кодирование, прикотором k бит исходного сообщения копируются в фиксированные k бит кодового слова, а затем вычисляютсяостальные m = n − k проверочных бит. При использовании систематического кодирования этап преобразования из декодированного кодового слова v̂ в декодированное сообщение û становится тривиальным. Рассмотримспособ систематического кодирования для линейного кода, заданного порождающей матрицей G. Очевидно,что с помощью эквивалентных преобразований столбцов матрица G может быть приведена к виду, в которомнекоторые k строк образуют единичную подматрицу. Пусть, не ограничиваяобщности, единичная подматрица Ikобразуется в первых k строках преобразованной матрицы G̃, т.е.

G̃ =, где Ik – единичная матрица размераPk×k, а P ∈ {0, 1}m×k . Тогда кодирование по правилу v = G̃u будет систематическим, при котором первые k биткодового слова v являются битами исходного сообщения u.Линейное пространство {0, 1}n может быть разложено в прямую сумму линейных подпространств C и C ⊥ ,где C ⊥ – ортогональное подпространство для C, dim C ⊥ = m. Пусть h0 , . . . , hm−1 ∈ {0, 1}n – базис C ⊥ . Составимматрицу T h0 hT1 H =  .

 ∈ {0, 1}m×n . .. hTm−1Очевидно, что hTj g i = 0 ∀i, j. Следовательно, для любого кодового слова v ∈ C выполнено Hv = 0. Матрица Hназывается проверочной матрицей кода. Проверочная матрица определена с точностью до эквивалентных преобразований строк. Рассмотрим процедуру построения систематической проверочной матрицы H по заданнойпорождающей матрицекода G. С помощью эквивалентных преобразований столбцов приведем порождающуюIkматрицу G к виду G̃ =.

Тогда проверочная матрица H может быть построена как H = P Im ∈ {0, 1}m×n ,Pгде Im – единичная матрица размера m×m. Действительно, в этом случае Hv = H G̃u = (P + P )u = 0.Таким образом, задание линейного кода требует рассмотрения порождающей матрицы размера n×k илипроверочной матрицы размера m×n (линейные требования по k и n). Каждая из этих матриц определена сточностью до эквивалентных преобразований столбцов или строк (соответствует произволу в выборе базиса впространствах C и C ⊥ ). Однако, фиксирование позиций бит при систематическом кодировании задаёт порождающую и проверочную матрицу однозначно.Пример 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.5 Однако,такой поиск d по-прежнему является экспоненциальным по k.Несистематическое кодирование находим непосредственно:10 0 111 0 11 0 0 [u1 , u2 ] = 0[v 1 , v 2 ] = 01 1 111 1 000 1 1101.01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0 1 01 1 01 1 10 1 1В последней матрице в строках (3, 5, 1) стоит единичная подматрица.

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

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

. . , v 8 ] = G[u1 , . . . , u8 ] =  0 0 1 1 0 0 1 1 = 0 1011 0 1 0 1 0 1 0 10 1 00 01 1 10 1всех 23 = 8 кодовых слов и000111110010011110101011011001101.100Отсюда получаем, что d = 3. Следовательно, рассмотренный код способен исправить одну ошибку и обнаружитьдве ошибки.Декодирование. Под процедурой декодирования будем понимать разбиение множества из всех 2n принятых сообщений w на 2k подмножеств, каждое из которых соответствует декодированию в своё кодовое слово.Назовём синдромом принятого сообщения w вектор s = Hw, s ∈ {0, 1}m , где H – проверочная матрица кода.С учётом представления w = v + e, получаем s = Hw = H(v + e) = Hv + He = He.

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

Заметим, что описанная процедура декодирования в синдромной формулировке полностью не зависитот конкретной схемы кодирования.Общая процедура декодирования линейного кода предполагает построение таблицы размера 2m ×n, в которойдля каждого синдрома принятого сообщения s записывается решение СЛАУ He = s с наименьшим хэмминговым весом.

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

Тип файла PDF

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

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

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