Спосіб декодування кодів з низькою щільністю контролю за парністю (ldpc) з використанням пам’яті і пристрій для здійснення способу

1. Пристрій для проведення операцій декодування кодів з низькою щільністю контролю за парністю (LDPC), який містить: блок обробки контрольних вершин, який включає в себе пам'ять станів контрольних вершин, яка включає в себе множину елементів зберігання в пам'яті станів повідомлень для множини контрольних вершин, причому кожний елемент зберігання стану контрольної вершини відповідає одній контрольній вершині і включає в себе першу і другу комірки для зберігання першого і другого значень модуля повідомлення, що зберігаються, які відповідають повідомленням, що направляються в контрольну вершину, якій відповідає згадана пам'ять станів контрольних вершин, при цьому кожний елемент зберігання стану контрольної вершини також включає в себе комірку пам'яті знака, призначену для зберігання значення накопиченого знака, який відповідає контрольній вершині, якій відповідає елемент зберігання стану контрольної вершини, і елемент обробки контрольної вершини, призначений для оновлення стану, що зберігається в пам'яті станів контрольних вершин, на основі вмісту повідомлення, що приймається, від вершини змінної до контрольної вершини, та блок керування, з'єднаний з пам'яттю станів контрольних вершин, для видачі стану контрольної вершини, який відповідає тій самій контрольній вершині, що і повідомлення, що обробляється, від вершини змінної до контрольної вершини, причому стан контрольної вершини видається з одного з елементів зберігання станів контрольних вершин, який відповідає тій самій вершині, що і повідом 2 (19) 1 3 86987 4 ру графа коду LDPC, що використовується для омлень в комірку пам'яті, з якої була виконана викерування кодуванням. бірка інформації про стан повідомлень. 8. Пристрій за п. 1, в якому пам'ять станів контро18. Спосіб за п. 17, який також включає в себе польних вершин включає в себе один елемент зберіслідовне повторення етапів прийому, вибору, вигання в пам'яті стану контрольної вершини для бірки та оновлення для кожного з множини повідкожної контрольної вершини, включеної в структуомлень, що приймаються в першій послідовності, ру графа коду LDPC що використовується для яка відповідає порядку, в якому ребра, які відповікерування декодуванням. дають повідомленням, що приймаються, з’єднані з 9. Пристрій за п. 2, в якому пам'ять знаків повідомвершинами змінних, що обробляються, в графі, лень включає в себе одну комірку зберігання знаякий відображає код з LDPC. кового біта для кожного ребра повідомлення, 19. Спосіб за п. 18, в якому послідовність, яка відвключеного в структуру графа коду LDPC, що виповідає порядку, в якому ребра, які відповідають користовується для керування декодування. повідомленням, що приймаються, з'єднані з вер10. Пристрій за п. 9, який також містить блок оброшинами змінних, що обробляються, в графі, який бки вершин змінних, з'єднаний з блоком обробки відображає код з LDPC, відрізняється від другої контрольних вершин, причому блок обробки верпослідовності, в якій ребра, які відповідають повідшин змінних приймає повідомлення від контрольомленням, що приймаються, з'єднані з вершинами них вершин до вершин змінних з блока обробки змінних, що обробляються, в графі, який відобраконтрольних вершин і генерує повідомлення від жає код з LDPC. вершин змінних до контрольних вершин, що пода20. Спосіб за п. 18, який також включає в себе ються в блок обробки контрольних вершин. здійснення операції витягування повідомлення від 11. Пристрій за п. 10, який також містить блок кеконтрольної вершини до вершини змінної щонайрування декодером, з'єднаний з блоком обробки менше на одному наборі інформації про стан, яка контрольних вершин і з блоком обробки вершин відповідає контрольній вершині, для якої прийнязмінних, причому блок керування декодером керує тий повний набір повідомлень від вершин змінних і блоком обробки контрольних вершин, і блоком до контрольних вершин. обробки вершин змінних, для обробки повідом21. Спосіб за п. 20, який також включає в себе лень в порядку вершин змінних. здійснення операції витягування для генерування 12. Пристрій за п. 11, в якому блок обробки вермножини повідомлень від контрольних вершин до шин змінних включає в себе множину паралельно вершин змінних, при цьому повідомлення від контрозташованих елементів обробки вершин змінних. рольних вершин до вершин змінних, що направ13. Пристрій за п. 12, в якому блок обробки контляються в окрему одну з множини вершин змінних, рольних вершин включає в себе множину паралегенерують послідовно для одержання послідовнольно розташованих елементів обробки контрольсті повідомлень від контрольних вершин до верних вершин. шин змінних, що направляється в окрему одну з 14. Пристрій за п. 13, в якому є щонайменше один множини вершин змінних. елемент переупорядкування повідомлень, розта22. Спосіб за п. 16, який також включає в себе пошований між блоком обробки вершин змінних і вне завершення оновлення стану першої контроблоком обробки контрольних вершин, призначельної вершини для генерування набору повністю ний для переупорядкування повідомлень, що пеоновленого стану, який відповідає першій контроредаються паралельно між блоком обробки верльній вершині, перед завершенням оновлення шин змінних і блоком обробки контрольних стану щонайменше однієї іншої контрольної вервершин. шини, причому оновлення стану для контрольної 15. Пристрій за п. 14, в якому блок керування девершини є повністю завершеним, коли стан для кодером включає в себе керуючу логічну схему контрольної вершини оновлений один раз для кодля керування елементом переупорядкування жного з множини ребер повідомлень, які відповіповідомлень залежно від інформації про переуподають контрольній вершині. рядкування повідомлень, що зберігається. 23. Спосіб за п. 16, який також включає в себе 16. Спосіб проведення операцій декодування кодів оновлення ще одного набору стану, який відповіз низькою щільністю контролю за парністю, який дає першій контрольній вершині, як частини другої включає в себе етапи, на яких зберігають в пам'яті ітерації обробки повідомлень від вершин змінних інформацію про стан повідомлень, яка відповідає до контрольних вершин перед тим, як повністю повідомленням, що приймаються множиною контзавершується згадане оновлення стану щонаймерольних вершин, приймають повідомлення, що нше однієї контрольної вершини. вводиться, для контрольної вершини, направлене 24. Спосіб за п. 23, який також включає в себе був одну з множини контрольних вершин, на основі феризацію повністю оновленого стану, який відпоконтрольної вершини, в яку направлено повідомвідає першій контрольній вершині, і витягування лення, що приймається, вибирають один з множиповідомлень від контрольних вершин до вершин ни наборів інформації про стан для використання змінних з буферизованого повністю оновленого на операції оновлення стану, здійснюють вибірку з стану. пам'яті вибраного набору інформації про стан по25. Спосіб за п. 24, який також включає в себе гевідомлень і оновлюють вибраний набір інформації нерування множини вихідних повідомлень з повніпро стан повідомлень залежно від повідомлення, стю оновленого стану та інформації про знаки, що що приймається. зберігається, що відповідає множині повідомлень 17. Спосіб за п. 16, який також включає в себе завід вершин змінних до контрольних вершин, що пис оновленого набору інформації про стан повід 5 86987 6 використовуються для генерування повністю оновершин змінних з оновленої інформації про стан, вленого стану. яка відповідає першій множині контрольних вер26. Спосіб за п. 16, який також включає в себе пошин, протягом другого періоду часу. вне завершення оновлення станів для першої 31. Спосіб за п. 30, в якому перший і другий перімножини контрольних вершин перед завершенням оди часу однакові за тривалістю. оновлень станів, які відповідають другій множині 32. Спосіб за п. 30, в якому перший і другий періконтрольних вершин, при цьому оновлення стану оди часу відділені один від одного третім періодом для контрольної вершини є повністю завершеним, часу, протягом якого відбувається оновлення стаколи стан для контрольної вершини оновлений ну, який відповідає третьому набору контрольних один раз для кожного з множини ребер повідомвершин. лень, які відповідають контрольній вершині. 33. Спосіб за п. 30, в якому кожна з першої і другої 27. Спосіб за п. 26, в якому кожна з першої і другої множин контрольних вершин включає в себе щомножин контрольних вершин включає в себе щонайменше 10 % контрольних вершин в графі, який найменше 20 % загальної кількості контрольних відповідає коду з LDPC, що використовується для вершин в графі коду з LDPC, який відображає керування декодуванням. структуру коду з LDPC, яка втілюється, що викори34. Спосіб за п. 30, в якому кожна з першої і другої стовується для керування декодуванням. множин контрольних вершин включає в себе що28. Спосіб за п. 16, в якому операцію оновлення найменше 20 % контрольних вершин в графі, який здійснюють як частину оновлення інформації про відповідає коду з LDPC, що використовується для стан, яка відповідає першій множині контрольних керування декодуванням. вершин. 35. Спосіб за п. 30, в якому перший період часу 29. Спосіб за п. 28, в якому оновлення першої становить менше 40 % того часу, який потрібний множини контрольних вершин здійснюють протядля обробки N повідомлень від вершин змінних до гом першого періоду часу з використанням першоконтрольних вершин, де N дорівнює сумарній кільго набору повідомлень від вершин змінних до конкості ребер повідомлень в графі, який відповідає трольних вершин, при цьому спосіб також включає коду з LDPC, що використовується для керування в себе оновлення інформації про стан, яка відподекодуванням. відає другій множині контрольних вершин під час 36. Спосіб за п. 30, в якому перший період часу другого періоду часу, причому друга множина констановить менше 20 % того часу, який потрібний трольних вершин включає в себе тільки контрольні для обробки N повідомлень від вершин змінних до вершини, які не включені в першу множину контконтрольних вершин, де N дорівнює сумарній кільрольних вершин, при цьому другий період часу іде кості ребер повідомлень в графі, який відповідає за першим періодом часу. коду з LDPC, що використовується для керування 30. Спосіб за п. 29, який також включає в себе видекодуванням. тягування повідомлень від контрольних вершин до Майже у всіх формах електронних систем зв'язку і зберігання даних використовуються коди з виправленням помилок. Коди з виправленням помилок компенсують ненадійність передачі інформації, що вноситься, в цих системах, шляхом внесення надмірності в потік даних. Математичні основи виправлення помилок були закладені Шенноном. Шеннон розробив математичну ідею каналу, відповідно до якої спотворення сигналів в системах зв'язку моделюється як стохастичний процес. Найбільш важливим результатом Шеннона є теорема про канал з шумом, яка визначає для каналу «пропускну здатність» - якість, яка конкретно вказує максимальну швидкість, з якою можна надійно передавати інформацію по каналу. Надійна передача на швидкостях, що наближаються до пропускної здатності, вимагає використання кодів з виправленням помилок. Таким чином, коди з виправленням помилок призначені для досягнення достатньої надійності при одночасному як можна більшому наближенні до пропускної здатності. Складність втілення коду з виправленням помилок є додатковим фактором, який набирає чинності в практичних прикладеннях кодів з виправленням помилок. Останні досягнення в системах кодування з виправленням помилок, що є результатом винаходу турбо-кодів і подальшого повторного відкриття і розробки кодів з низькою щільністю контролю за парністю (LDPC), дозволяють запропонувати системи кодування з гнучкою складністю, що дозволяють досить близько підійти до пропускної здатності за Шенноном. Коди з LDPC добре відображаються дводольними графами, які часто називають графами Таннера, такими, як граф 100, показаний на Фіг.1. У графах Таннера одна множина вершин - вершини 102 «змінних» - відповідає бітам кодового слова, а інша множина вершин - вершини 106 «обмежень», які іноді називають «контрольними» вершинами, відповідають множині обмежень контролю за парністю, які і визначають код. Ребра 104 в графі зв'язують вершини змінних з вершинами, обмежень. Вершина змінної і вершина обмеження називаються сусідами, якщо вони з'єднані ребром в графі. Звичайно передбачають, що дві вершини з'єднані щонайменше одним ребром. Коди з LDPC можна еквівалентно представити, скориставшись матрицею 202 контролю за парністю. На Фіг.2 наведений приклад представлення матриці контролю за парністю, при цьому вектор «х», позначений позицією 206, є кодовим словом, якщо і тільки якщо Нх=0. 7 86987 8 З кожною вершиною змінної зв'язаний один біт ня алгоритмів передачі повідомлень. Існує багато кодового слова. У деяких випадках, деякі з цих потенційно корисних алгоритмів передачі повідомбітів можуть бути «виколоті». Виколоті біти можуть лень, так що використання таких алгоритмів не бути бажаними в деяких структурах кодів, і вони обмежується декодуванням кодів з LDPC. виключаються з кодового слова, що передається. Щоб полегшити розуміння винаходу, що розПослідовність бітів, що має однозначну відпоглядається в нижченаведених розділах, наведемо відність з послідовністю вершин змінних, є кодотепер короткий математичний опис довірчого повим словом коду, якщо і тільки якщо для кожної ширення. вершини обмеження біти, що сусідують з цим обДовірче поширення для (двійкових) кодів з меженням (за допомогою свого зв'язку з вершинаLDPC можна виразити таким чином. Повідомленми змінних) в сумі дають нуль по модулю два, тобня, що передаються по ребрах графа, інтерпретуто є парна кількість таких бітів. ються як логарифмічні правдоподібності Iog(p0/p1), Декодери та алгоритми декодування, що викоде рх означає імовірність того, що біт буде приристовуються для декодування кодових слів, які ймати значення «х». Біти м'якого рішення, що наскладаються з кодів з LDPC, працюють, обмінююдаються декодеру приймачем, також задаються в чись повідомленнями в межах графа по ребрах і формі логарифмічної правдоподібності. Таким оновлюючи ці повідомлення шляхом проведення чином, значення, що приймаються, тобто елеменобчислень у вершинах на основі вхідних повідомти слова, що приймається, являють собою логалень. Такі алгоритми далі будуть узагальнено імерифмічні правдоподібності відповідних бітів, зумонуватися алгоритмами передачі повідомлень. Ковлені спостереженням бітів, що надаються жна вершина змінної в графі спочатку забезпечена каналом зв'язку. У загальному випадку, повідомбітом м'якого рішення, який називається «значенлення m представляє логарифмічну правдоподібням, що приймається» і вказує оцінку відповідного ність m, а значення «у», що приймається, предзначення біта, що визначається шляхом спостеставляє логарифмічну правдоподібність «у». Для режень, наприклад, за каналом зв'язку. В ідеальпроколотих бітів значення «у» логарифмічної праному випадку, оцінки для окремих бітів статистичвдоподібності, що приймається, задають рівним 0, но незалежні. На практиці, цей ідеал може вказуючи, що р0=р1=1/2. порушуватися, а часто - і порушується. Набір знаРозглянемо правила передачі повідомлень чень, що приймаються, складає «слово, що призгідно з довірчим поширенням. ймається». У контексті цієї заявки, словом, що Повідомлення позначаються символом m C2V, приймається, можна визначити сигнал, що спостеякщо це повідомлення від контрольних вершин до рігається, наприклад, приймачем в системі зв'язку. вершин змінних, і символом mV2C, якщо це повідКількість ребер, з'єднаних з вершиною, тобто омлення від вершин змінних до контрольних вервершиною змінної або вершиною обмеження, нашин. Розглянемо вершину змінної з d ребрами. зивається «ступінь» вершини. «Однорідним» граНехай для кожного ребра j=1,...,d символ mC2V(i) фом або кодом є той, для якого всі вершини змінозначає вхідне повідомлення на ребрі і. При ініціаних мають один і той самий ступінь, скажемо, j, і лізації процесу декодування задамо mC2V=0 для всі вершини обмежень мають один і той самий кожного ребра. У загальному випадку, вихідні поступінь, скажемо, k. В цьому випадку можна сказавідомлення з вузлів змінних задаються таким чити, що код є (j, к)-однорідним кодом. Це були коди, ном: які першим розглянув Галлагер (Gallager, 1961). На відміну від «однорідного» коду, неоднорідний код має вершини обмежень і/або вершини змінних Вихідне кодоване значення м'якого рішення з з різними ступенями. Наприклад, деякі вершини вершини (не повідомлення на ребрі), яке відповізмінних можуть мати ступінь 4, інші - ступінь 3, а дає цій операції задається таким чином: ще одні - ступінь 2. Хоча представлення і/або втілення неоднорідних кодів може виявитися складнішим, показано, що неоднорідні коди з LDPC можуть забезпечити Вихідне тверде рішення, зв'язане з цим значудові робочі параметри виправлення та виявленченням, що виводиться, одержується із знаку для ня помилок в порівнянні з однорідними кодами з xout. LDPC. У контрольних вершинах часто зручніше предПотрібно зрозуміти, що слова, що приймаютьставляти повідомлення з використанням їх «знася, генеровані відповідно до кодування кодами з ків» і модулів. Тому нехай для повідомлення m LDPC, можна обробляти, проводячи на цих словах вираз m р є GF[2] означає «парність» повідомленоперацію декодування кодів з LDPC, наприклад, ня, тобто mр = 0, якщо m≥0, і mр=1, якщо m