3.6. Распределение весов и границы вероятности ошибки

В общем случае, распределение весов двоичного линейного (n,k) кода С может быть найдено перечислением всех 2^к кодовых слов и подсчетом их веса Хемминга. Очевидно, что при больших k это нереализуемая затея. Обозначим A_w число кодовых слов веса Хемминга w. Тождество Мак-Вильямc связывает распределение весов линейного кода, А(х) = А₀ + А₁х + А₂х² +...+ А_nxⁿ , с распределением весов дуального ему (n, n-k) кода С┴, В(х) = B₀ + В₁х + В₂х² +... + В_nxⁿ, следующим соотношением:

(3.27)

которое может быть записано и в обращенной форме

(3.28)

Таким образом, для кодов с высокой скоростью проще сначала подсчитать распределение весов дуального кода, а затем вычислить А(х) по формуле (3.27).

Для некоторых классов кодов может быть использована решетчатая структура кода. Для кодов меньшей длины распределение весов нетрудно посчитать с помощью тождества Мак-Вильямс. Далее вводится определение расширенного циклического кода. Двоичный расширенный циклический код получается из циклического кода добавлением, в начале (или, наоборот, в конце) каждого кодового слова, общей проверки на четность. Расширенный код уже не является циклическим. Пусть Н проверочная матрица циклического кода, тогда проверочная матрица Н_ext расширенного кода равна

(3.29)

Для расширенных БЧХ кодов известно, что A^(ext)_n+1-w = A^(ext)._w Эти данные полезны для нахождения распределения весов двоичного циклического БЧХ кода длины до 127. Это делается с помощью следующего результата.

Пусть С двоичный циклический (п, k) БЧХ код с распределением весов А(х), полученный исключением общей проверки из двоичного расширенного (n+1, k) с распределением весов А^(eхt)(х). Тогда для четного веса w справедливо соотношение:

(3.30)

Пример 39. Рассмотрим двоичный расширенный (8,4,4) код Хемминга. Этот код имеет проверочную матрицу (см. также Пример 23)

Легко проверить, что А^(ext)(х) = 1 + 14x⁴ + х⁸. Для распределения весов двоичного циклического (7, 4, 3) кода Хемминга получаем с помощью (3.30)

3.6.1. Оценка вероятности ошибки

Известный спектр весов кода позволяет оценить его вероятности ошибки, как это обсуждалось в части 1. Распределение весов и граница объединения (1.34) дают хорошую оценку вероятности ошибки кода при передаче двоичных сигналов по каналу с АБГШ.

На Рисунке 28 представлена граница объединения (1.40) для канала с общими Релеевскими замираниями и распределения весов из приложения А для БЧХ кода длины 8. Граница посчитана с помощью метода Монте-Карло при замене коэффициента A_w на wA_w/n чтобы учесть двоичные ошибки. Границы для других кодов могут быть получены аналогичным способом.

Рис. 24. Оценки BER по границе объединения для расширенных БЧХ кодов длины 8. Двоичный канал с АБГШ.

Рис. 25. Оценки BER по границе объединения для расширенных БЧХ кодов длины 32. Двоичный канал с АБГШ.

Рис. 26. Оценки BER по границе объединения для расширенных БЧХ кодов длины 16. Двоичный канал с АБГШ.

Рис. 27. Оценки BER по границе объединения для расширенных БЧХ кодов длины 64. Двоичный канал с АБГШ.

Рис. 28. Оценки BER по границе объединения для расширенных БЧХ кодов длины 8. Двоичный канал с общими Релеевскими замираниями.

Главный вывод этого раздела состоит в следующем. Прежде чем выбирать конкретный алгоритм мягкого декодирования имеет смысл использовать распределение весов кода и границу объединения для предварительной оценки эффективности, достижимой в заданном канале. Для каналов с АБГШ и Релеевскими замираниями граница объединения дает точный ответ для вероятности ошибки на бит менее 10^-4.

Вопросы для самоконтроля

1. Какие коды называются СRС кодами?

2. Какой порождающий многочлен у кода СRС-12?

3. Какой порождающий многочлен у кода СRС-16?

4. Какой порождающий многочлен у кода СRС-CCITT?

5. Какой порождающий многочлен у кода СRС-32?

6. Когда линейный блоковый код является циклическим?

7. Что называют порождающим полиномом g(x) циклического кода?

8. Как найти проверочный полином бинарного циклического кода?

9. Запишите формулу несистематического кодирования двоичного циклического кода.

10. Запишите формулу систематического кодирования двоичного циклического кода.

11. Найдите значение выражения x⁶mod(x³+x+1)?

12. Найдите значение выражения x⁵mod(x³+x+1)?

13. Найдите значение выражения x⁴mod(x³+x+1)?

14. Найдите значение выражения x³mod(x³+x+1)?

15. Как найти неприводимые делители бинома (х^п — 1)?

16. Что такое БЧХ коды?

17. Как найти количество проверочных символов необходимых для коррекции заданного количества ошибок?

18. Что такое граница БЧХ?

19. Из каких блоков состоит архитектура БЧХ декодера?

20. Как лучше рассматривать алгоритм Берлекемпа-Мэсси?

21. Какой алгоритм лежит в основе декодера PGS?

22. Какая процедура лежит в основе алгоритма Евклида?

23. Какое название получил метод поиска корней а(х) на множестве локаторов позиций кодовых символов?

24. Что подразумевается под процессом стирания символа?

25. Можно ли подсчитать распределение весов кода по его дуальному коду. ?

26. Оцените, в каких приделах лежит вероятность ошибки на информационный бит BER (если BER = 4) расширенных БЧХ кодов длины 8 при передаче по двоичным каналам с АБГШ.

27. Оцените, в каких приделах лежит вероятность ошибки на информационный бит BER (если BER = 4) расширенных БЧХ кодов длины 32 при передаче по двоичным каналам с АБГШ.

28. Оцените, в каких приделах лежит вероятность ошибки на информационный бит BER (если BER = 4) расширенных БЧХ кодов длины 16 при передаче по двоичным каналам с АБГШ.

29. Оцените, в каких приделах лежит вероятность ошибки на информационный бит BER (если BER = 4) расширенных БЧХ кодов длины 64 при передаче по двоичным каналам с АБГШ.