Введение в теорию кодирования
 Скачать 0.91 Mb.
|
|
Каким образом действует декодер? • Ищет в таблице полученное на выходе канала связи слово y, например, y = (1101). • Принимает решение, что вектор ошибок e — это лидер класса смежности, со- держащего вектор y, т. е. e = (1000). • Далее вектор y декодируется в вектор x = y − e = (1101) + (1000) = (0101) и делается вывод, что исходное сообщение было равно (01). Очевидно, что декодирование, использующее стандартное расположение, являет- ся декодированием по максимуму правдоподобия. Если линейный код имеет небольшие параметры, то таблица стандартного распо- ложения очень удобна для процесса декодирования. Но в большинстве случаев такая процедура неэффективна, так как требует большого объема вычислений. Например, 2.2. Декодирование линейных кодов 23 если взять линейный код длины 100 и размерности 70, то таблица декодирования содержит 2 70 столбцов и 2 30 строк, т. е. имеет очень большие размеры. Процесс декодирования может быть упрощен с помощью синдромов. Для деко- дирования достаточно выписать лидеры смежных классов и соответствующие им синдромы. После того как получен вектор y, вычисляется его синдром. Далее отыс- кивается лидер смежного класса a i с тем же синдромом и вычитание этого лидера из вектора y x = y − a i дает предположительно посланный вектор x. 2.2.2. Свойства синдрома 1. Если проверочная матрица имеет (n − k) строк, то синдром S y произвольного вектора y ∈ E n является вектором длины (n − k). 2. Поскольку по определению линейного кода вектор y является кодовым тогда и только тогда, когда Hy T = 0, то справедливо Утверждение 5. Синдром S y вектора y равен 0 тогда и только тогда, когда y является кодовым вектором. 3. Справедливо Утверждение 6. Для двоичного линейного кода синдром S y принятого вектора y равен сумме тех столбцов проверочной матрицы H, где произошли ошибки. Доказательство. Пусть получен вектор y = x + e, где x — кодовый вектор. Тогда, по определению синдрома и из утверждения 5, имеем S y = Hy T = H(x + e) T = Hx T + He T = He T . Пусть e имеет "1" в координатах с номерами i 1 , i 2 , . . ., i s , т. е. supp(e) = {i 1 , i 2 , . . . , i s } Это означает, что произошли ошибки в i 1 , i 2 , . . . , i s координатах. Таким образом, имеем He T = s X k=1 e i k h i k = h i 1 + h i 2 + . . . + h i s , где h i k — это i k -й столбец матрицы H. Следовательно, S y = s X k=1 h i k , т. е. действительно синдром выделяет те позиции вектора, где произошли ошибки. N 4. Имеет место взаимно однозначное соответствие между синдромами и смежны- ми классами. 24 Глава 2. Декодирование Утверждение 7. Два вектора u и v принадлежат одному и тому же смеж- ному классу тогда и только тогда, когда их синдромы равны. Доказательство. Два элемента группы u и v принадлежат одному и тому же смежному классу по данной подгруппе тогда и только тогда, когда u−v принадлежит этой подгруппе. В нашем случае подгруппой является код C, т. е. u − v ∈ C. Тогда по определению линейного кода выполняется H(u − v) T = 0. Отсюда Hv T = Hu T N Таким образом, синдром содержит всю информацию, которую имеет декодер об ошибках: по принятому слову y вычисляется синдром S y . По утверждению 6 син- дром равен сумме тех столбцов проверочной матрицы, где произошли ошибки. По синдрому ищется лидер смежного класса, то есть вектор ошибок и далее — кодовое слово. Рассмотрим вычисление синдрома для приведенного выше примера. Сначала по порождающей матрице G найдем проверочную матрицу H: G = µ 1 0 1 1 0 1 0 1 ¶ −→ H = µ 1 0 1 0 1 1 0 1 ¶ . Затем вычислим синдром для смежного класса с лидером (1000), он равен µ 1 1 ¶ , т. е. первому столбцу матрицы H. Далее вычислим все синдромы и запишем их в таблицу синдромов. Сообщение Лидер Синдром Код 0000 µ 0 0 ¶ Первый смежный класс 1000 µ 1 1 ¶ Второй смежный класс 0100 µ 0 1 ¶ Третий смежный класс 0010 µ 1 0 ¶ Пусть получено слово y = (1100). Вычислим его синдром: Hy T = µ 1 0 1 0 1 1 0 1 ¶ 1 1 0 0 = µ 1 0 ¶ , он равен третьему столбцу проверочной матрицы H. Ему отвечает лидер смежного класса (0010), он же является искомым вектором ошибок, т. е. x = y − (0010) = (1100) ⊕ (0010) = (1110). Отсюда делаем вывод, что было передано кодовое слово (1110). 2.3. Вероятность ошибки декодирования 25 Упражнение 17. Построить таблицу стандартного расположения для кода с проверочной матрицей 0 1 1 1 0 0 1 0 1 0 1 0 1 1 0 0 0 1 и декодировать два произвольных вектора, один непосредственно с помощью табли- цы стандартного расположения, другой вектор — с помощью таблицы синдромов. 2.3. Вероятность ошибки декодирования Определение. Вероятностью ошибки декодирования или вероятностью ошиб- ки на слово P ош для данной схемы декодирования называется вероятность появления некодового слова на выходе декодера. Пусть дан линейный код длины n мощности M с кодовыми словами {x 1 , . . . , x M }, где кодовые слова используются с равной вероятностью. Обозначим вероятность то- го, что на выходе декодера получено слово y 6= x i при переданном x i через P (y 6= x i |x i ). Тогда P ош = 1 M M X i=1 P (y 6= x i |x i ), т. е. вероятность ошибки на слово равна средней вероятности неправильного декоди- рования. При декодировании, использующем стандартное расположение, правильное деко- дирование имеем тогда и только тогда, когда вектор ошибок совпадает с лидером смежного класса. Иначе говоря, вероятность ошибки в этом случае равна P ош = P {e 6= лидер смежного класса}. Если имеем α i лидеров смежных классов веса i, i = 0, . . . , n, то вероятность правильного декодирования P пр.дек. равна P пр.дек. = n X i=0 α i p i (1 − p) n−i , (2.1) поскольку вероятность правильного декодирования кодового слова с некоторым век- тором ошибок v веса i равна p i (1 − p) n−i (см. разд. 2.1.). Так как стандартное расположение обеспечивает декодирование по максимуму правдоподобия, то любая другая схема будет иметь вероятность правильного деко- дирования меньше, чем (2.1), а следовательно, и вероятность ошибки произвольная 26 Глава 2. Декодирование схема декодирования будет иметь не меньше, чем вероятность ошибки при декоди- ровании, использующем стандартное расположение, поскольку P ош = 1 − P пр.дек. = 1 − n X i=0 α i p i (1 − p) n−i . (2.2) Для кода, приведенного выше, имеем α 0 = 1, α 1 = 3. Таким образом, при p = 1 100 получим P ош = 1 − (1 − p) 4 − 3p(1 − p) 3 = 0, 0103 . . . . Рассмотрим линейный код с минимальным расстоянием d = 2t + 1. По теореме 3 он исправляет t ошибок и, следовательно, каждый вектор веса не больше t является лидером смежного класса, т. е. α i = C i n , 0 ≤ i ≤ t. Если вероятность p ошибки в канале очень мала, то (1 − p) ≈ 1 и, следовательно, p i+1 (1 − p) n−i−1 = o(p i (1 − p) n−i ). Отбрасывая в равенстве (2.2) все члены, начиная с i > t, получаем формулу, аппроксимирующую формулу (2.2) достаточно точно: P ош ∼ 1 − t X i=0 C i n p i (1 − p) n−i . (2.3) Аналогично в случае кодового расстояния d = 2t + 2 получаем следующую ап- проксимацию формулы (2.2): P ош ∼ 1 − t X i=0 C i n p i (1 − p) n−i − α t+1 p t+1 (1 − p) n−t−1 . (2.4) Если α i = 0 при i > t = b(d − 1)/2c, то формула (2.3) становится точной; при i > t + 1 становится точной формула (2.4). В первом случае код называется совершенным, во втором — квазисовершенным. Геометрически это означает, что в первом случае имеем разбиение пространства E n на непересекающиеся шары радиуса t (так как код может исправлять не больше, чем t ошибок). Во втором случае, поскольку код исправляет все ошибки веса не больше t, некоторые ошибки веса t + 1 и не может исправлять ни одной ошибки веса больше, чем t + 1, имеем покрытие пространства E n шарами радиуса t + 1. При этом шары радиуса t + 1 могут пересекаться. Более тонкой мерой качества декодирования является вероятность ошибки на символ. Пусть имеем линейный код мощности M = 2 k с кодовыми словами x 1 , . . . , x M , где первые k символов x i 1 , . . . , x i k в каждом слове являются информационными. Пусть y = (y 1 , . . . , y n ) — слово на выходе декодера. Определение. Вероятность ошибки на символ P симв. равна средней вероятности того, что после декодирования информационный символ является ошибочным: P симв. = 1 kM k X j=1 M X i=1 P {y j 6= x i j |x i было послано}. 2.3. Вероятность ошибки декодирования 27 Вернемся к декодированию стандартным расположением. Так как все сообще- ния и ошибки в любом символе независимы и равновероятны (т. е. рассматривается симметричный канал), то достаточно рассмотреть произвольный кодовый вектор x = (x 1 , . . . , x n ). Пусть получен вектор y, тогда P симв. = 1 k k X j=1 P {y j 6= x i j }. Пусть f (e) — число неправильных информационных символов после декодирования при условии, что e — вектор ошибок, тогда P симв. = 1 k X e f (e)P {e}. (2.5) Рассмотрим наш пример: изучая таблицу стандартного расположения, приходим в выводу, что f (e) = 0 для всех векторов ошибок первого столбца, так как в первом столбце стоят лидеры смежных классов; f (e) = 1 для всех векторов ошибок как второго, так и третьего столбцов; f (e) = 2 для всех векторов четвертого столбца. Отсюда по формуле (2.5) при p = 1/100 получаем P симв. = 1 2 h 1 · ¡ p 4 + 3p 3 (1 − p) + 3p 2 (1 − p) 2 + p(1 − p) 3 ¢ + 2 · ¡ p 3 (1 − p) + 3p 2 (1 − p) 2 ¢i = = 0,00530 . . . . Глава 3 Теорема Шеннона 3.1. Необходимые понятия Рассмотрим двоичный симметричный канал связи. Пусть для каждого символа имеется вероятность 0 < p < 1 2 того, что при передаче его по каналу связи про- изойдет ошибка. Пусть C — двоичный код, содержащий M равновероятных кодовых слов x 1 , . . . , x M длины n, в котором каждое слово встречается с равной вероятно- стью. Напомним, что вероятностью ошибки на слово или вероятностью ошибки P C для данной схемы декодирования называется вероятность появления неправильного кодового слова на выходе декодера. Пусть P i — вероятность неправильного декоди- рования при условии, что передано кодовое слово x i . Тогда P C := 1 M M X i=1 P i , где P i зависит от вероятности p. Рассмотрим совокупность e L всех двоичных кодов длины n мощности M и определим P ∗ (M, n, p) := min C∈e L {P C }. (3.1) Определение. Функция энтропии H(x) определяется равенством H(x) = −x log x − (1 − x) log(1 − x) при 0 < x < 1, при x = 0 и x = 1 полагают H(0) = H(1) = 0. Отметим, что log x здесь и далее рассматривается по основанию 2. Определение. Пропускная способность двоичного симметричного канала с ве- роятностью 0 ≤ p ≤ 1 2 равна C(p) = 1 − H(p) = 1 + p log p + (1 − p) log(1 − p). Определение. Скоростью (n, M, d)-кода называется величина (log M)/n. Теорема 11 (Шеннон К., 1948). Пусть R — любое число, удовлетворяющее условию 0 < R < C(p), и пусть M n = 2 [n·R] . Тогда P ∗ (M n , n, p) → 0 при n → ∞. 28 3.2. Свойства энтропии 29 Теорему Шеннона можно переформулировать следующим образом: для любой сколь угодно малой величины ε > 0 и любого 0 < R < C(p) существует двоичный код C длины n, мощности M и скорости R такой, что вероятность ошибки декодирования P C < ε, где M определяется из соотношения R = (log M)/n. Или, говоря неформально, для достаточно больших n существует хороший код длины n, со скоростью, сколь угодно близкой к пропускной способности канала связи. Прежде чем доказать теорему, рассмотрим несколько важных свойств энтропии по Шеннону и приведем необходимые понятия и утверждения, которые будут ис- пользоваться в доказательстве теоремы Шеннона. 3.2. Свойства энтропии Рассмотрим бернуллиевский источник A: буквы входного алфавита a i , i = 1, . . . , k появляются независимо с независимыми вероятностями p i , удовлетворяющими усло- вию k X i=1 p i = 1. Энтропия H(A) источника A по Шеннону определяется следующим образом: H(A) = − k X i=1 p i log p i . В определенной выше энтропии H(x) имеем два исхода с вероятностями p и 1 − p соответственно. Рассмотрим несколько важных свойств энтропии. Утверждение 8. Справедливо H(A) ≥ 0. Энтропия неотрицательна и равна нулю тогда и только тогда, когда одна из вероятностей равна единице, а остальные равны нулю. Доказательство. Действительно, из 0 ≤ p i ≤ 1 имеем 1 p i ≥ 1 и log 1 p i ≥ 0, т. е. − log p i ≥ 0, отсюда −p i log p i ≥ 0. Поскольку, по определению, −p i log p i = 0 при p i = 0, то для любого p i ≥ 0 выполняется −p i log p i ≥ 0 и, следовательно, H(A) = − k X i=1 p i log p i ≥ 0. При H(A) = 0 каждое слагаемое равно нулю, а значит, либо p i = 0, либо log p i = 0, т. е. p i = 1. Так как P k i=1 p i = 1, то среди вероятностей p i принять значение 1 может лишь одна, остальные равны нулю. Таким образом, неопределенность события рав- на нулю тогда и только тогда, когда исход события заранее известен, в остальных случаях энтропия положительна. N Рассмотрим произвольную непрерывную выпуклую вверх функцию |