Інші алгоритми декодування
У цьому розділі ми представляємо ряд важливих алгоритмів передачі повідомлень, які є наближеннями алгоритму sum-product. Тут не показано повний перелік таких алгоритмів, але тут охоплено більшість алгоритмів, які будуть використовуватись у наступних розділах цієї роботи.
В алгоритмі min-sum метод коригування на змінному вузлі такий самий, як у алгоритмі sum-product (2.9), але метод коригування на перевірочному вузлі спрощується
Зверніть увагу, що результат апроксимується як мінімум абсолютного значення результуючого знака. Ця апроксимація стає більш точною величиною, коли величина повідомлення збільшується. Таким чином, у наступних ітераціях, коли величина повідомлення зазвичай велика, ймовірність помилкового декодування цього алгоритму є майже такою самою, як і алгоритму sum-product.
Алгоритм А декодування Галлагера:
У цьому алгоритмі, введеному Галлагер [11], повідомлення належить алфавіту . Іншими словами, використовується не програмна інформація.
Правило коригування на перевірочному вузлі:
де ⨁ подає суму за модулем два двійкових повідомлень.
На змінному вузлі вихідне повідомлення таке ж, як і внутрішнє повідомлення, якщо всі зовнішні повідомлення не згодні з внутрішнім повідомленням. У цьому випадку вихідне повідомлення таке саме, як і зовнішні повідомлення. Іншими словами
де є внутрішнім двійковим повідомленням і є доповненням до двійкової величини .
У частині цієї роботи ми посилаємося на алгоритм А декодування Галлагера. Алгоритм має найгірше виконання в порівнянні з програмними методами декодування, введеними вище, але обчислювально набагато менш складний.
Алгоритм Б декодування Галлагера:
Цей алгоритм також належить Галлагеру і, подібно до алгоритму А, всі повідомлення мають двійкове значення. Єдина різниця між цим алгоритмом та Алгоритм А це метод коригування змінного вузла. На змінному вузлі вихідне повідомлення
де ціле число в діапазоні. Тут вихідне повідомлення змінного вузла таке ж, як внутрішнє повідомлення, крім зовнішніх повідомлень, що суперечать один одному. Значення може змінюватись від однієї ітерації до іншої. Оптимальне значення для рівномірного LDPC коду обчислюється по Галлагеру [11], і найменше число , для якого
де і перехідні ймовірності каналу (внутрішня величина помилки у повідомленні) та зовнішня величина помилки у повідомленні, відповідно. З цього моменту ми посилатимемося на алгоритм Галлагера Б як на алгоритм Б.
Ми доведемо у розділі 3, що алгоритм Б є найкращим із можливих алгоритмів передачі двійкових повідомлень рівномірних кодів LDPC. Для нерівномірних LDPC кодів, ми також покажемо, що алгоритм Б найоптимальніший серед усіх двійкових алгоритмів передачі повідомлень, коли вузли в фактор графі коду не мають інформації про вузлові ступені в їхньому місцевому районі.
В обох алгоритмах А та Б, повідомлення не несуть програмну інформацію. Тому не дивно, що ймовірність помилкового декодування цих двох алгоритмів у порівнянні з алгоритмом sum-product низької якості. Але, звичайно, вони обчислювально набагато дешевші. У міру того, як програма декодера (наприклад, декодер sum-product) прагне напряму зближення, величина повідомлень стає дуже великою, тому програмна інформація стає менш корисною. Ми використовуємо цю особливість у розділі 7, щоб прискорити процес декодування, дозволяючи декодер вибрати свій метод декодування на кожній ітерації, і мипобачимо, що декодер прагне перейти на алгоритми апаратного декодування у наступних ітераціях.
LDPC коди: аналіз
Перш ніж вивчати методи аналізу LDPC кодів, ми обговоримо принцип ітеративного декодування, щоб зрозуміла мета такого аналізу.
Мал. 2.4. Принцип ітеративного декодування.
Ітеративний декодер на кожній ітерації використовує два джерела інформації кодового слова, що передається: інформація з каналу (внутрішня інформація), а також інформацію з попередньої ітерації (зовнішня інформація). Від цих двох джерел інформації алгоритм декодування намагається отримати більш якісну інформацію про кодове слово, що передається, за допомогою цих даних як зовнішньої інформації для наступної ітерації (див. рис. 2.4). У успішному декодуванні зовнішня інформація стає дедалі краще в міру того, як декодер робить ітерацію. Таким чином, у всіх методах аналізу ітеративного декодера статистика зовнішніх повідомлень на кожній ітерації вивчається.
Вивчення еволюції PDF-функцій із зовнішніх повідомлень, по черзі перебираючи кожну ітерацію, є найповнішим аналізом (відомий як щільність еволюції). Однак, як наближений аналіз можна простежити за еволюцією представників цієї щільності.
Аналіз LDPC кодів Галлагера
У початкових роботах Галлагера LDPC коди вважалися рівномірними і декодування передбачало використання бінарних повідомлень (алгоритми А і Б). Галлагер проводив аналіз декодера у таких ситуаціях [11]. Основною ідеєю його аналізу є характеристика величини помилок у повідомленнях у кожній ітерації з погляду ситуації у каналі та величини помилки у повідомленнях у попередній ітерації. Іншими словами, при аналізі Галлагера, еволюція величини помилки вповідомленнях вивчається, вона також еквівалентна щільності еволюції, тому що PMF-функція двійкових повідомлень є одновимірною, тобто вона може бути описана одним параметром.
Мал. 2.5. Дерево декодування глибини один для рівномірного (3, 6) коду LDPC.
Аналіз Галлагера виходить з припущенні, що вхідні повідомлення на перемінний (перевірочний) вузол є незалежними. Хоча це припущення правильне, тільки якщо граф без циклів, це доведено в [12], де очікувана ймовірність помилкового декодування коду зводиться до нагоди без циклів у міру збільшення довжини блоку коду.
Дерево декодування
Розглянемо скориговане повідомлення від змінного вузла ступеня перевірки вузла в декодері. Це повідомлення обчислюється з вхідних повідомлень та канального повідомлення до Ті вхідні повідомлення насправді є вихідними повідомленнями деяких вузлів перевірок, які коригуються раніше. Розглянемо одне з таких повідомлень разом із його перевірним вузлом ступеня. Вихідне повідомлення цього вузла перевірки розраховується з вхідних повідомлень до . Можна повторити цю процедуру для всіх вузлів перевірок, пов'язаних з , щоб сформувати дерево декодування однієї глибини. Приклад такого дерева декодування для рівномірного (3, 6) коду LDPC показаний на рис. 2.5. Продовжуючи так само, можна отримати дерево декодування будь-якої глибини. На рис. 2.6 показаний приклад дерева декодування глибини два для нерівномірного коду LDPC. Очевидно, що для нерівномірних кодів декодування дерев з коренем на різних змінних вузлах по-різному.
Мал. 2.6. Дерево декодування глибини два для нерівномірного коду LDPC.
Зверніть увагу, що коли фактор граф є деревом, повідомлення в дереві декодування будь-якої глибини незалежні.Якщо фактор граф має цикли та його обсяг, то до глибини повідомлення в дереві декодування є незалежними. Таким чином, незалежне припущення є вірним до ітерацій і є наближеним для подальших ітерацій.