Способи і пристрій ldpc-декодування

1. LDPC-декодер, який містить: джерело повідомлень, що включає в себе вихід повідомлень для видачі N повідомлень паралельно, при цьому N більше 1; модуль обробки вузлів, що включає в себе N процесорів вузлів, розміщених паралельно; керований блок перестановки, який зв'язує згадане джерело повідомлень із згаданим модулем обробки вузлів, причому згаданий керований блок перестановки включає в себе вхід сигналу керування переупорядковуванням для прийому сигналу керування переупорядковуванням, щоб керувати переупорядковуванням повідомлень в щонайменше одному наборі з N повідомлень, що передаються через згаданий керований блок перестановки; керуючий модуль для формування першого сигналу керування адресацією як функції від збереженої інформації опису кодів, причому згаданий керуючий модуль має вихід першого сигналу керування адресацією, сполучений із згаданим джерелом повідомлень; і модуль вибору блоків для формування сигналу вибору адрес блоків, причому згаданий модуль вибору блоків має вихід сигналу вибору адрес блоків, сполучений із згаданим джерелом повідомлень. 2. Декодер за п. 1, в якому згаданий керуючий модуль включає в себе: лічильник внутрішніх циклів для формування згаданого першого сигналу керування адресацією; і лічильник зовнішніх циклів для формування сигналу керування зовнішніми циклами, який видається в згаданий модуль вибору блоків, причому згаданий лічильник зовнішніх циклів одержує приріст як 2 (19) 1 3 вузла, який перемикається між режимом роботи вузлів змінних і перевірних вузлів. 13. Декодер за п. 12, в якому кожний з конфігурованих процесорів вузлів приймає конфігураційну інформацію, що формується за допомогою згаданого керуючого модуля із згаданої збереженої інформації опису коду. 14. Спосіб виконання обробки декодування з контролем по парності низької щільності (LDPC), який включає етапи, на яких: надають декодер, що включає в себе: модуль пам'яті, який включає в себе NxLxK комірок пам'яті, де N і L - позитивні цілі числа, а K ціле число більше 1, причому кожна комірка пам'яті забезпечує збереження декількох бітів; керований модуль перестановки, сполучений із згаданим модулем пам'яті, для виконання операцій переупорядковування елементів для набору з N багатобітових елементів, щоб змінити порядок елементів в згаданому наборі; модуль обробки вузлів, який включає в себе N конфігурованих процесорів вузлів, розміщених паралельно, сполучений із згаданим керованим модулем перестановки; набір збережених інструкцій керування декодером; і формують перший сигнал переупорядковування, який використовується для керування доступом до пам'яті, як функцію від інструкції керування декодером, включеної в згаданий набір збережених інструкцій керування декодером; і формують другий сигнал керування переупорядковуванням як функцію від згаданої інструкції керування декодером, причому згаданий другий сигнал керування переупорядковуванням подають в згаданий модуль перестановки. 15. Спосіб за п. 14, який додатково включає етапи, на яких: виконують операцію доступу до пам'яті в комірці, визначеній з першого сигналу керування переупорядковуванням; і впливають на модуль перестановника для виконання операції переупорядковування повідомлень відповідно до згаданого поданого сигналу керування переупорядковуванням. 16. Спосіб за п. 15, в якому згаданий етап виконання операції доступу до пам'яті в комірці, визначеній із згаданого першого сигналу керування переупорядковуванням, включає в себе етапи, на яких: формують адресу пам'яті з першого значення керування адресацією, включеного в згадану команду керування декодером, і другого сигналу керування адресацією, сформованого із згаданого першого сигналу переупорядковування і значення, сформованого лічильником циклів. 17. Спосіб за п. 16, в якому значення, сформоване за допомогою згаданого лічильника циклів, формується як функція від сигналу індикатора довжини кодового слова. 18. Спосіб за п. 17, який додатково включає етап, на якому: конфігурують вузли в згаданому модулі обробки вузлів як функцію від інформації конфігурації, включеної в згадану команду керування декодером. 94695 4 19. Спосіб декодування інформації, раніше закодованої за допомогою LDPC-кодера, при цьому спосіб включає етапи, на яких: приймають інформацію довжини перших кодових слів, яка вказує довжину перших кодових слів, які повинні декодуватися; подають згадану інформацію про довжину кодових слів на керуючий вхід LDPC-декодера; впливають на LDPC-декодер, щоб приймати дані, які повинні декодуватися; і впливають на LDPC-декодер, щоб декодувати дані, що приймаються, як функцію від інформації, що приймається, про довжину кодових слів. 20. Спосіб за п. 19, який додатково включає етап, на якому: приймають інформацію довжини других кодових слів, яка вказує довжину додаткових кодових слів, які повинні декодуватися, причому згадана довжина додаткових кодових слів є другим числом бітів, яке відрізняється від першого числа бітів, вказаного за допомогою згаданої інформації довжини перших кодових слів. 21. Спосіб за п. 20, в якому згадана інформація довжини перших кодових слів являє собою сигнал першого вибраного коефіцієнта розширення коду, що використовується для указання кількості разів ітеративного виконання команд. 22. Спосіб за п. 19, який додатково включає етапи, на яких: зберігають перший набір інформації опису структури коду в модулі в згаданому декодері; і використовують збережений перший набір інформації опису коду для виконання операції LDPCдекодування. 23. Спосіб за п. 22, який додатково включає етап, на якому: зберігають другий набір інформації опису структури коду в згаданому модулі в згаданому декодері, причому другий набір інформації опису структури коду відповідає LDPC-коду, що має структуру, відмінну від структури коду, якій відповідає перший набір інформації про структуру коду. 24. Спосіб за п. 23, який додатково включає етапи, на яких: декодують дані за допомогою першого набору інформації про структуру коду при здійсненні зв'язку з першим пристроєм; і декодують дані за допомогою другого набору інформації про структуру коду при здійсненні зв'язку з другим пристроєм. 25. Спосіб за п. 24, в якому перший набір інформації про структуру коду використовується в момент часу, відмінний від моменту часу, коли використовується другий набір інформації про структуру коду. 26. Спосіб за п. 22, в якому згаданий етап збереження першого набору інформації опису коду виконується у відповідь на прийом сигналу, який вказує, що кодові слова, відповідні згаданому першому набору інформації опису коду, повинні декодуватися. 27. Спосіб за п. 22, в якому згаданий етап збереження першого набору інформації опису коду виконується у відповідь на прийом сигналу, що включає в себе кодові слова, кодовані згідно зі 5 94695 6 структурою коду, відповідною згаданому першому набору інформації опису коду. 28. Спосіб за п. 22, в якому згаданий перший набір інформації опису включає в себе інструкції керування декодером. 29. Спосіб за п. 28, в якому кожна інструкція керування декодером включає в себе покажчик операції читання або запису. 30. Спосіб за п. 29, в якому кожна інструкція керування декодером додатково включає в себе інформацію керування чергуванням. 31. Спосіб за п. 29, в якому кожна інструкція керування декодером додатково включає в себе інформацію адреси запам'ятовуючого пристрою. 32. Спосіб за п. 31, в якому кожна інструкція керування декодером додатково включає в себе інформацію конфігурації, яка вказує те, що блок обробки вузлів повинен конфігуруватися як блок обробки вузлів змінних або блок обробки перевірних вузлів. 33. Спосіб реалізації системи програмованого LDPC-декодера, який включає етапи, на яких: зберігають протягом першого періоду часу перший набір інструкцій декодування в модулі LDPCдекодера, причому згаданий перший набір інструкцій декодування відповідає першій структурі LDPC-коду; впливають на LDPC-декодер для виконання операції LDPC-декодування з використанням структури збережених інструкцій декодування; зберігають протягом другого періоду часу другий набір інструкцій декодування, причому згаданий другий набір інструкцій декодування відрізняється від згаданого першого набору і відповідає другій структурі LDPC-коду, яка відрізняється від згаданої першої структури LDPC-коду; і впливають на декодер для виконання операції LDPC-декодування з використанням збереженого другого набору інструкцій декодування. 34. Спосіб за п. 33, в якому перший і другий набори інструкцій декодування використовуються протягом різних періодів часу для виконання операцій декодування. 35. Спосіб за п. 33, в якому згаданий етап збереження першого набору інструкцій декодування виконується у відповідь на прийом сигналу, який вказує те, що повинні використовуватися кодові слова, відповідні згаданому першому набору інформації опису коду. 36. Спосіб за п. 33, в якому згаданий етап збереження першого набору інструкцій декодування виконується у відповідь на прийом сигналу, що включає в себе кодові слова, кодовані згідно зі структурою коду, відповідною згаданому першому набору інструкцій декодування. 37. Спосіб за п. 33, в якому згадані перший і другий набори інструкцій декодування зберігають в згаданому модулі протягом згаданого першого і другого періодів часу, причому згаданим модулем є пристрій пам'яті. 38. Спосіб за п. 37, в якому множина згаданих інструкцій керування декодером включає в себе покажчик дозволу/блокування операції запису. 39. Спосіб за п. 37, в якому кожна із згаданої множини інструкцій керування декодером включає в себе інформацію керування чергуванням. 40. Спосіб за п. 39, в якому кожна із згаданої множини інструкцій керування декодером додатково включає в себе інформацію адреси пам'яті. Галузь техніки, до якої належить винахід Даний винахід направлений на способи і пристрій для виконання операцій декодування з контролем по парності низької щільності (LDPC) і, більш конкретно, до способів декодування, які оптимально придатні для декодування даних, які відповідають кодовим словам, наприклад, кодовим словам, сформованим за допомогою структури коду, яка може бути виражена як розширення за допомогою добутку. Рівень техніки Коди корекції помилок повсюдно використовуються в системах зв'язку і зберігання даних. Останнім часом виник значний інтерес до класу кодів, відомого як коди з контролем парності низької щільності (LDPC). Доведено, що LDPC-коди є хорошими кодами. По різних каналах було продемонстровано, що LDPC-коди дійсно близькі до пропускної здатності каналу, тобто верхньої межі швидкості передачі, встановленій Шенноном. LDPC-коди часто представляються за допомогою дводольних графів (див. наведений для прикладу граф 100 на фіг. 1), званих графами Таннера, в яких один набір вузлів, вузли 102 змінних, відповідає бітам кодового слова, а інший набір вузлів, вузли 106 обмежень, іноді званий перевірочними вузлами, відповідає набору обмежень контролю парності, які визначають код. Ребра 104 на графі 100 з'єднують вузли 102 змінних з вузлами 106 обмежень. Вузол змінних і вузол обмежень вважаються сусідніми, якщо вони сполучені ребром на графі. Альтернативою представленню на графі Таннера LDPC-кодів є представлення матриці контролю парності N 202, фіг. 2. Бітова послідовність x 206 являє собою кодове слово, якщо і тільки якщо добуток бітової послідовності і N складається із всіх нулів, тобто: Нх=0. Бітова послідовність, пов'язана однозначно певним чином з вузлами змінних, являє собою кодове слово коду, якщо і тільки якщо для кожного вузла обмежень біти, сусідні з обмеженням (за допомогою їх зв'язку з вузлами змінних), в сумі дають нуль по модулю два, тобто вони містять парне число одиниць. У деяких випадках деякі з цих кодованих бітів можуть бути проколені (видалені) або відомі. Видалені біти можуть бути бажані в деяких структурах коду, і при розширеннях (див. нижче) як проколені, так і відомі біти можуть бути використані для одержання довжин блока, які не є кратними розширенню. Проколені біти і відомі біти можуть виключатися і часто виключаються з кодового слова, що передається. 7 Число ребер, приєднаних до вузла, тобто вузла змінної і вузла обмеження, згадується як ступінь вузла. Регулярний граф або код - це граф або код, для якого всі вузли змінних мають однаковий ступінь, наприклад, j, і всі вузли обмежень мають однаковий ступінь, наприклад, k. В цьому випадку кажуть, що код є регулярним кодом (j, k). Були коди, розглянуті спочатку Галлагером (1961). На відміну від «регулярного» коду, нерегулярний код має вузли обмежень або вузли змінних різних ступенів. Наприклад, деякі вузли змінних можуть мати ступінь 4, інші - ступінь 3, а ще одні - ступінь 2. Хоч нерегулярні коди можуть бути більш складні для їх представлення і/або реалізації, продемонстровано, що нерегулярні LDPC-коди можуть забезпечувати хороші характеристики корекції і виявлення помилок в порівнянні з регулярними LDPC-кодами. Зрозуміло, що слова, що приймаються, які формуються в зв'язку з LDPC-кодуванням, можуть оброблятися за допомогою виконання операцій LDPC-декодування над ними, наприклад, операцій корекції і виявлення помилок, щоб сформувати відновлену версію вихідного кодового слова. Відновлене кодове слово потім може піддаватися декодуванню даних для відновлення вихідних даних, які були закодовані. Процесом декодування даних може бути, наприклад, простий вибір конкретного піднабору бітів з відновленого кодового слова. Операції LDPC-декодування, загалом, містять алгоритми передачі повідомлень. Існує множина потенційно корисних алгоритмів передачі повідомлень, і використання цих алгоритмів не обмежено LDPC-декодуванням. Принцип алгоритму передачі повідомлень полягає в тому, що кожний вузол ітеративно обмінюється даними з сусідніми вузлами через з'єднуюче ребро відносно свого представлення для біта, пов'язаного з ребром, представлення наступної ітерації в залежності від представлень про поточну ітерацію, що приймаються. LDPC-коди з великою довжиною блока, які відповідають великим структурам графів, надають множину переваг в порівнянні з меншими кодами у відношенні стійкості до помилок. Щоб реалізувати велику структуру графа за допомогою меншого графа, різні перестановки можуть бути застосовані до копій меншої структури графа, і копії можуть бути пов'язані для реалізації більшої структури графа. При операціях декодування ці операції перестановки можуть бути реалізовані за допомогою комутуючого пристрою, що згадується в даному документі як перестановник (блок перестановок), який застосовує операцію перестановки до елементів, наприклад, повідомлень, у разі операції декодування, по мірі того, як вони проходять між запам'ятовуючим пристроєм і блоком векторної обробки, який паралельно виконує LDPC-операції. Хоча відомі різні реалізації LDPC-декодера, залишається потреба в способах і пристрої, які можуть зменшити витрати на реалізацію апаратних засобів LDPC-декодера і підвищити гнучкість LDPC-декодера відносно числа LDPC-кодів, які він може декодувати, і довжини кодових слів, які мо 94695 8 жуть бути декодовані за допомогою LDPCдекодера. Суть винаходу Даний винахід направлений на LDPCдекодери і, більш конкретно, на LDPC-декодери, які можуть бути реалізовані апаратно ефективним способом і/або які забезпечують міру свободи за рахунок підтримки декодування кодових слів різної довжини і/або кодових слів, відповідних різним структурам коду. У деяких, але не в усіх варіантах здійснення даного винаходу LDPC-декодер даного винаходу зроблений програмованим. За рахунок зміни коду, наприклад, мікрокоду, що використовується для керування роботою декодера, можливе декодування кодових слів, сформованих згідно з різними структурами коду. Пристрій, наприклад, пристрій зв'язку, такий як безпровідний термінал, що включає в себе декодер згідно з даним винаходом, може зберігати керуючий код, який описує різні структури коду. На основі інформації, що приймається в потоці зв'язку або від користувача, код, відповідний LDPC-кодованим даним, які повинні прийматися і оброблятися, ідентифікується і витягується із запам'ятовуючого пристрою. Потім код завантажується в декодер і використовується для керування декодуванням в залежності від структури коду, визначеної відповідно до даних, які повинні декодуватися. У деяких варіантах здійснення в декодер завантажується керуючий код (наприклад, мікрокод), відповідний одній попередньо вибраній структурі коду, яка повинна використовуватися пристроєм для керування декодуванням. Хоч керуючий код може бути фіксованим в конкретному варіанті здійснення, той же керуючий код може бути використаний, відповідно до винаходу, для декодування кодових слів різних розмірів аж до максимального розміру кодового слова, що визначається максимальним об'ємом пам'яті або регістрів, доступних для підтримки декодування кодового слова. У залежності від розміру кодового слова, кількість разів виконання керуючої команди, збереженої в декодері, може варіюватися. Індикатор розміру кодового слова, який може бути виражений як вибраний коефіцієнт розширення коду, може бути використаний для указання декодеру розміру кодового слова, яке повинно декодуватися. Індикатор розміру кодового слова звичайно вказує розмір кодового слова через кратне мінімального розміру блока. Хоч різні декодери згідно з даним винаходом підтримують програмованість для забезпечення можливості декодування даних, закодованих згідно з різними структурами LDPC-коду і кодовими словами різної довжини, способи і пристрій згідно з даним винаходом також можуть бути використані для реалізації декодера, який виконує операції LDPC-декодування над даними, сформованими згідно з однією структурою коду і розміром одного кодового слова. Тобто способи і пристрої, відповідні винаходу, корисні навіть у випадках, коли програмованість і підтримка кодових слів різної довжини не є проблемою. 9 Різні варіанти здійснення даного винаходу направлені на дані, закодовані за допомогою структур коду, які можуть бути виражені як LDPC-графи, які мають певну ієрархічну структуру, в якій повний LDPC-граф представляється, переважно, складеним з декількох копій, Z, наприклад, в Ζ раз меншого графа, де Ζ - це ціле число. Ζ копій графа можуть бути ідентичними. Для цілей пояснення винаходу менший граф згадується як проекція графа, повний граф як розширений граф, a Z - як коефіцієнт розширення. Розглянемо індексацію проекцій LDPC-графів як 1,..., j,..., Z. У вузлах змінних суворо паралельного графа на графі j сполучені тільки з вузлами обмежень на графі j. У відповідності з даним винаходом, береться одне векторне ребро, що включає в себе одне відповідне ребро, кожне з кожної копії графа, і виконується перестановка в межах Ζ ребер, наприклад, дозволяється перестановка, наприклад, не переупорядковування вузлів обмежень, відповідних ребрам в межах векторного ребра. Можна обмежити перестановки в просторі піднабору (звичайно групи) матриць перестановки ΖxΖ, позначеного як Ψ. Передбачається, що інверсії перестановок в Ψ також знаходяться в Ψ. Під набір Ψ, загалом, може вибиратися за допомогою різних критеріїв. Одне з основного мотивування вищезгаданої структури полягає в тому, щоб спростити апаратну реалізацію декодерів і кодерів. Отже, може бути вигідно обмежити Ψ перестановками, які можуть бути ефективно реалізовані в апаратних засобах, наприклад, в схемі комутації. У патенті США 6633856 описана архітектура LDPC-декодера, яка використовує перевагу розширеної структури. У цій архітектурі векторизується процес декодування. Більш конкретно, дозволяється перестановка Ζ ребер в межах векторного ребра або обмін між копіями проекції графа по мірі того, як вони проходять, наприклад, зі сторони вузлів змінних до сторони вузлів обмежень. У процесі проходження (декодування) векторизованих повідомлень, відповідних Ζ паралельним проекціям графа, цей обмін реалізовується за допомогою перестановки повідомлень в рамках векторного повідомлення по мірі того, як воно проходить з однієї сторони векторизованого графа до іншої. Нижче коротко розглянута, наведена для прикладу, реалізація векторизованого декодера. Передбачається, що пам'ять, яка зберігає повідомлення від вузла змінних до перевірочних вузлів і/або повідомлення від перевірочного вузла до вузлів змінних, скомпонована в ΖxΕ m-бітових комірок пам'яті, де Ε - це число ребер, a m - це число бітів, що переносяться в повідомленні, ціле число більше 1. Доступ до пам'яті здійснюється в Ζ mбітовому блоці, іншими словами, при кожному доступі зчитується або записується Ζ m-бітовий блок. Цей Ζ m-бітовий блок відповідає Ζ повідомленням по Ζ розширених ребрах розширеного графа. Для зручності опису кожний набір з Ζ m-бітових повідомлень асоціюється з відповідним ребром в проекції графа. Наприклад, здійснення доступу до повідомлень ребра є в проекції графа, фактично відповідає здійсненню доступу до Ζ m-бітових по 94695 10 відомлень, відповідних Ζ ребрам в розширеному графі. Згідно із загальним алгоритмом передачі повідомлень оновлення повідомлення у вузлі залежить від всіх повідомлень від сусідніх об'єктів даного вузла. Нехай вузол в проекції має d ребер е1, е2,..., ed. Заснована на ребрах реалізація оновлення повідомлень може зчитувати повідомлення е 1, застосовувати відповідне переупорядковування; після чого переупорядковані повідомлення знаходяться в належних сусідніх угрупуваннях для всіх Ζ вузлів розширеного графа. У патенті США 6633856 архітектура декодера має Ζ паралельних блоків обробки для здійснення обробки вузлів. У одному або більше каскадах, повідомлення можуть піддаватися перетворенню формату для забезпечення ефективної реалізації. Наприклад, різні формати можуть використовуватися на стороні вузлів змінних і на стороні перевірочних вузлів. Перевага векторного декодера полягає в тому, що він досягає високої пропускної здатності за рахунок забезпечення структурованого паралелізму. Структура розширення компактним чином виконує опис паралельних блоків обробки, оскільки оновлені Ζ вузлів відповідають одному вузлу в проекції графа, і всі їх сусідні ребра відповідають одному ребру в проекції графа, відповідно. Опис розширеного (векторного) декодера звичайно веде за собою зберігання інформації про переупорядковування і вузли, пов'язаної з кожним ребром, крім опису невеликого графа (проекції), що використовується для визначення структури більшого графа. При умові, що кожне ребро має постійний розмір опису, загальна вимога по зберіганню інформації декодера пропорційна числу ребер в графі проекції. Для зручності опису назвемо цей набір інформації опису декодера керуючим кодом, який також іноді згадується як мікрокод декодування розширеного графа. Отже, для ідентичної довжини блока збільшення коефіцієнта розширення, як правило, скорочує розмір мікрокоду декодування. Для великої довжини блока це може значно знижувати об'єм пам'яті для зберігання мікрокоду. У мікрокоді половина описує обробку вузлів змінних, а інша половина описує обробку перевірочних вузлів. Процес декодування виконує кожну половину мікрокоду послідовно, причому кожна позначається як половина ітерації декодування. Варіанти здійснення в патенті США 6633856 включають в себе структури, що виконують дві половини (при цьому обробка вузлів змінних є однією половиною, а обробка перевірочних вузлів є іншою половиною) ітерації LDPC-декодування, відомі як одна повна ітерація, альтернативно або одночасно. Успішне декодування звичайно пов'язане з декількома повними ітераціями, наприклад, можуть бути потрібними декілька ітерацій доти, поки обробка декодування не приведе до модифікації кодового слова, що приймається, до точки, де воно сходиться до відомого кодового слова. Один елемент векторизованої паралельної обробки - це модуль переупорядковування, що спрощується за допомогою схеми комутації. Внутрішнє сполучання Ζ копій здійснюється за допомо 11 гою використання модуля переупорядковування. Після переупорядковування повідомлень обробка містить просто Ζ паралельних блоків, кожний з яких відповідає копії проекції графа. Векторний (розширений) LDPC-декодер з паралелізмом Ζ реалізації, реалізований відповідно до винаходу, досягає в Ζ разів більшої пропускної здатності в порівнянні з декодером з паралелізмом 1. Компроміс полягає в тому, що він вимагає приблизно в Ζ разів більше логічних схем в аспекті апаратної складності. Хоч установлення паралелізму реалізації на коефіцієнт розширення для розширеного графа є зручною, це необов'язково. У багатьох випадках це може бути небажаним. Наприклад, передбачимо, що великий коефіцієнт Ζ розширення використовується при описі великого графа для вищезазначеної переваги економії пам'яті для зберігання мікрокоду. Установлення паралелізму реалізації рівним коефіцієнту Ζ розширення приводить до надмірної пропускної здатності. З урахуванням того факту, що апаратна складність пропорційна паралелізму реалізації, а складність опису графа пропорційна коефіцієнту Ζ розширення, бажано встановлювати паралелізм реалізації таким чином, щоб результуюча пропускна здатність відповідала вимозі без надмірності, при використанні розширеного графа, що описується більшим коефіцієнтом Ζ розширення. Це вигідно як для складності блока обробки, так і для пам'яті для опису декодера. Даний винахід направлений на способи і пристрій реалізації векторного LDPC-декодера з паралелізмом N реалізації, з використанням опису декодера з коефіцієнтом Ζ розширення, де Ν - це дільник Ζ. Паралелізм N реалізації може вибиратися відповідно до необхідної пропускної здатності, тим самим використовуючи мінімальну апаратну складність. Це досягається таким чином. При заданому мікрокоді для розширеного графа з коефіцієнтом Ζ=ΚxΝ розширення даний винахід визначає декодер з паралелізмом N реалізації, який розширює кожну ітерацію декодування до K ітерацій. Кожна ітерація проходить через весь мікрокод один раз, виконуючи 1/K ітерації декодування з паралелізмом Ζ реалізації. Оскільки передбачено N паралельних блоків обробки, загальне значення часу обробки в результаті виходить таким же, що і очікувалося. По суті, паралельна обробка переводиться в послідовну обробку без зміни мікрокоду, шляхом опису декодера з використанням коефіцієнта N розширення. Більше того відповідно до даного винаходу, векторний LDPC-декодер з паралелізмом N реалізації допускає декодування класу LDPC-кодів з однаковою швидкістю, але різними розмірами кодових слів, з одного мікрокоду, що описує декодер з коефіцієнтом Ζ розширення. Конкретно, як приклад передбачимо, що якщо Ζ може бути розкладено на K1xK2xN, і розмір коду проекції графа дорівнює n, де Z, К1, К2, N і n - це позитивні цілі числа, то декодер може декодувати три різних коди з розмірами блока Νxn, Κ2xΝxn і Κ1xΚ2xΚ2xΝxn. 94695 12 Різні додаткові ознаки, вигоди і переваги даного винаходу описуються в подальшому докладному описі. Короткий опис креслень Фіг. 1 ілюструє представлення дводольного графа зразкового регулярного LDPC-коду з довжиною, що дорівнює десяти. Фіг. 2 - матричне представлення коду, графічно проілюстрованого на фіг. 1. Фіг. 3 і 4 ілюструють ідею розкладання виконання простого набору мікрокоду на K кроків. Фіг. 5 ілюструє зразкову архітектуру декодера відповідно до даного винаходу. Фіг. 6 ілюструє пристрій, наприклад, мобільний вузол, якийвикористовує програмований LDPCдекодер, реалізований відповідно до даного винаходу. Фіг. 7, яка складається з фіг. 7А і фіг. 7В, блок-схема способу роботи пристрою зв'язку відповідно до даного винаходу для виконання кодування і декодування відповідно до даного винаходу. Докладний опис винаходу Даний винахід направлений на LDPCдекодери і, більш конкретно, на LDPC-декодери, які можуть бути реалізовані апаратно ефективним способом. Способи і пристрій декодування, відповідні даному винаходу, можуть бути реалізовані як програмовані пристрої і/або пристрої, які можуть приймати інформацію індикатора довжини кодового слова і декодувати кодові слова різної довжини. Таким чином, хоч декодери, відповідні даному винаходу, можуть бути реалізовані як стаціонарні пристрої, що використовуються для декодування кодових слів конкретної довжини кодового слова, вони забезпечують деяку міру свободи за рахунок підтримки декодування кодових слів різної довжини і/або кодових слів, відповідних різним структурам коду. Патентна заявка США 10/788115, озаглавлена "METHOD AND APPARATUS FOR PERFORMING LOW-DENSITY PARITY-CHECK (LDPC) CODE OPERATIONS USING A MULTI-LEVEL PERMUTATION", від 26 лютого 2004 року, яка включена в даний документ за допомогою посилання, описує способи розширення за допомогою добутку, які можуть бути використані з LDPCкодами. Розширення за допомогою добутку додатково обмежує групу матриць перестановки ZxZ групами, які можуть бути розкладені на прямий добуток підгруп. Наприклад, передбачимо, що Ψ є прямим добутком двох груп, тобто Ψ=Ψ1xΨ2. Розмірність Ψ дорівнює добутку розмірностей Ψi, де Ψi - група матриць перестановки KixKi, де Ki - це ціле число. Додатково передбачається, що розмірність групи Ψi дорівнює розмірності матриці всередині групи, таким чином, Ζ=Κ1xΚ2. Відповідно до даного винаходу група Ψ розширення обмежена групою, розширеною за допомогою добутку. Розширення за допомогою добутку альтернативно може розглядатися як багатовимірне розширення. Припустимо, що проекція коду має розмір Р, тобто з Ρ вузлами змінних. Можна вибрати циклічну групу розміром 64 для розширення. Альтернативним відповідно до винаходу 13 повинен бути добуток циклічної групи розміром 16 і циклічної групи розміром 4. Ця група може бути представлена таким чином. Розглянемо індексацію L=0,..., 63 з використанням пар (a, b), а=0,..., 15 і b=0,..., 3 за допомогою оборотного відображення L=4a+b. Елементом цієї групи добутку є пара (с, d), з = 0,..., 15 і d=0,..., 3. Дія (с, d) на (а, b) полягає в тому, щоб переставити пару (а, b) з утворенням (а+с mod 16, d+b mod 4). Ця група також має порядок 64. Однак, результуючий розширений граф може інтерпретуватися як розширення коду розміром 4P на 16 або коду розміром 16Р на 4, або коду розміром Ρ на 64. Переваги, що пропонуються розширеннями за допомогою добутку, реалізовуються в контексті декодера, відповідного винаходу. Корисність, обумовлена використанням розширень за допомогою добутку, є ознакою винаходу. Розширення за допомогою груп, які не є добутками, наприклад, за допомогою циклічної групи, забезпечують можливість розширень довільного розміру, але не забезпечують гнучкості розширень за допомогою добутку. Патентна заявка США 10/788115, яка включена в цей документ за допомогою посилання, описує графи, розширені за допомогою добутку, і потенційні вигоди використання цих графів. Даний винахід доповнює базові принципи, описані у вищезазначеній заявці. Зокрема, ця заявка описує спосіб і пристрій реалізації декодера з використанням коефіцієнта Ζ=ΚxΝ розширення, а також відповідний спосіб і пристрій декодування графа з паралелізмом N реалізації, де К, N і Ζ цілі числа, і Ν