 |
Методы кодирования канала. Линейные блоковые коды. Коды Хемминга. Коды Голея
|
|
|
|
Методы кодирования канала
Линейные блоковые коды
Линейные блочные (блоковые) коды разделяют данные на группы длиной k и заменяют их уникальными кодовыми словами длиной n, где n больше чем k. Другими словами, линейные коды заменяют все двоичные числа от 0 до 2k (2k уникальных чисел) на кодовые слова от 0 до 2n. Полный набор 2k кодовых слов называют кодом, и его длина обычно обозначается М. Линейным этот код делает следующее свойство – любая линейная комбинация двух из 2k кодовых слов дает тоже кодовое слово. Например, код состоит из кодовых слов 00000, 10101, 10010 и 00111, выполняя операцию «исключающую или» (xor) для кодовых слов 10101 и 10010 получаем 00111. Это справедливо для всех комбинаций кодовых слов входящих в данный код.
Эти коды классифицируются по нескольким основным критериям. Расстояние Хэмминга (Hamming distance) между любыми 2-я двоичными кодовыми словами – это количество бит, которые отличаются в этих словах. Например, расстояние Хемминга между 10101 и 10000 - это 2, так как отличаются 3-й и 5-й биты. Минимальное кодовое расстояние – наименьшее расстояние Хемминга из всех пар кодовых слов. Вес Хемминга кодового слова - количество элементов отличных от нуля в коде. Для кода 10101, вес Хемминга – 3. Минимальный вес всего кода – это наименьший вес Хемминга от всех кодовых слов, и обозначается d. Для данного минимального расстояния, dmin, количество исправимых ошибок может быть выражено как ec = (dmin – 1)/2, и количество определяемых ошибок – как ed = dmin – ec – 1, при условии, что ec < = ed. Линейные блоковые коды часто обозначаются символьным рядом, где С представляет код, и C = {c1, c2, …, cM}. Обычно для обозначения атрибутов кода используют запись (n, k, d). Примеры линейных блоковых кодов – коды Хемминга и Галлея.
|
|
|
Коды Хемминга
Коды Хемминга это специальное подмножество линейных блоковых кодов. Для некоторого целого m > = 2, n = 2m – 1, k = 2m – m - 1, с минимальным расстоянием, равным 3. Поэтому из выражения для Rc = (2m – m - 1)/(2m – 1) видно, что Rc стремится к 1, при увеличении m. Для больших значений m, коды Хемминга могут быть использованы с минимальным увеличением полосы пропускания исходного сигнала. Оказывается, что при dmin = 3, все одиночные биты ошибок могут быть найдены и исправлены. Коды Хемминга, также уникальны тем, что их кодовые слова имеют биты четности в номерах битов, которые являются степенями двойки, в то время как все другие позиции содержат биты данных. Расположение бита четности определяет биты данных, предназначенных для вычисления четности, (операция xor), при этом пропускаются биты перед разрядом четности, затем проверяются n-1 бит после него, затем проверяются следующие n бит, и т. д.
Пример: Код замещения для 1010 может быть вычислен при размещении в 3-ем, 5-ом, 6-ом и 7-ом битах кода 1, 0, 1, 0 соответственно. Позиции этих двоичных разрядов не являются степенью 2. Тогда, первый бит (четность) кода должен быть установлен, используя операцию «исключающую или» (xor) с 3-им, 5-ым, и 7-ым битами, второй бит – xor с 3-им, 6-ым, и 7-ым битами, и четвертый бит – xor с 5-ым, 6-ым, и 7-ым битами, в результате получим код замещения 1011010.
После приема кода декодер должен повторно вычислить каждый из битов четности. Если один бит четности неверен, то этот бит должен быть изменен на обратный при передаче, и на него можно не обращать внимания. Если больше одного бита четности неправильны, то сумма позиций неправильных битов четности укажет позицию информационного разряда, в котором произошла ошибка. Ошибки в нескольких битах дадут неправильный результат.
В LabVIEW при использовании Modulation Toolkit коды Хемминга могут быть получены с помощью ВП Hamming Encoder и декодированы с помощью ВП Hamming Decoder.
|
|
|
Коды Голея
Коды Голея принадлежат к алгоритмам, которые используют конечные случайные группы для кодирования данных. Существует два различных типа кодов Голея, бинарный и троичный. Бинарная версия относится к классу (23, 12, 7) с минимальным расстоянием 7. Она может исправить и обнаружить все трехбитные ошибки. С добавлением бита четности, получится бинарный код Голея (24, 12, 8). Этот расширенный код Голея может обнаружить все четырехбитные ошибки и исправить все трехбитные ошибки. Троичный код Голея относится к классу (11, 3, 5) и может обнаружить и исправить все 2-битные ошибки.
Из-за их относительной неэффективности и превосходного обнаружения ошибок коды Голея чаще всего используются в приложениях, где пропускная способность не является определяющей, а главное – обеспечение надежности. Они используются в космической связи. В LabVIEW при использовании Modulation Toolkit коды Галея могут быть получены с помощью ВП Golay Encoder и декодированы с помощью ВП Golay Decoder.
|
|
|
