Category: образование

U-124

На всякого мудреца довольно простоты

Недавно наши американский спутник уронили. И правильно, так их, буржуев, а то напридумывали всякие технические штучки, панимашь. Например, стали использовать в блочных турбокодах вместо Хемминга (31, 26) код БЧХ (31, 21), исправляющий две ошибки.

И как его декодировать на старом железе? На самом деле, всё просто. Полином БЧХ-кода, исправляющий t ошибок есть произведение t минимальных полиномов.

Согласно http://www.finetune.co.jp/~lyuka/technote/ecc/ , полином для Хемминга (31, 26): x^5+x^2+1. Если он является делителем полинома БЧХ (31, 21) (x^10+x^9+x^8+x^6+x^5+x^3+1), декодирование тривиально: декодируется код Хемминга (31, 26) и отбрасываются лишние 5 проверочных битов.

Проверим:
10 9 8 6 5 3 0 |_ 5 2 0
10 7 5            5 4 3 2 0
------
   9 8 7 6 3 0
   9 6 4
   -----
     8 7 4 3 0
     8 5 3
     -----
       7 5 4 0
       7 4 2
       -----
         5 2 0
         5 2 0
         -----
             -


Как и следовало ожидать, полиномы разделились без остатка.

Всегда в практике помехоустойчивого кодирования поражала какая-то запредельная простота алгоритмов --- что-то на уровне арифметики первого класса школы. Плавающая точка заменяется целыми числами, умножения --- суммированием логарифмов и т.п. No rocket science.