Як розшифрувати БЛ?
Розпізнаний текст, спецсимволи та формули можуть містити помилки, тому з коректним варіантом рекомендуємо ознайомитись на відсканованих зображеннях підручника вище
Також, радимо скористатися пошуком по сайту, ми впевнені, що ви зможете знайти більше інформації щодо потрібної Вам тематики
6.7.
Коди Боуза, Чоудхурі і Хоквінгема відкриті Хоквінгемом (1959) і незалежно від нього Боузе і Чоудхурі (1960), являють собою клас циклічних кодів, які мають дуже потужну здатність виправляти помилки і одночасно припускають прості алгоритми декодування. коди, але абсолютно аналогічно можна як алфавіт вибирати елементи довільного поля Галуа Породжувальний багаточлен для цих кодів визначається в термінах деякого розширення поля Нехай а - елемент мультиплікативний порядок якого дорівнює числа довільні цілі числа; його багаточлен, що породжує, визначається рівністю
де означає найменше загальне кратне.
Довжина блоку в коді за визначенням дорівнює мультиплікативному порядку елемента. послідовність, що повністю складається з нулів, за визначенням, вибирається як єдине кодове слово.
Інше визначення БЧХ-коду з параметрами, зазначеними вище, полягає в тому, що послідовність є кодовим словом тоді і тільки тоді, коли є корінням. , ділиться на отже, на всі мінімальні багаточлени.
відповідного кодового слова. Назад, якщо багаточлен не є кодовим словом, то він не ділиться на отже, не ділиться, принаймні, на один з мінімальних багаточленів, припустимо, але тоді а не є коренем
У більшості програм як а вибирається примітивний елемент так що якість зазвичай вибирається 1. Пізніше буде показано, що параметр має сенс нижньої межі для мінімальної відстані в коді.
приклад. Так як введені вище визначення, без сумніву, здаються дещо абстрактними, розглянемо конкретний приклад. Нехай використовується уявлення, визначене таблицею на рис. 6.6.3. Виберемо як елемент а той елемент на рис. 6.6.3, який представляється багаточленом Як показано в § 6.6, мінімальний багаточлен для а над дорівнює Тоді з (6.6.13) випливає, що елементам відповідає той же мінімальний багаточлен, що і елементу а. Як показано в § 6.6, мінімальний багаточлен для рівний
Цікава особливість, яку розкриває даний приклад, полягає в тому, що при і за будь-яких маємо.
Так як ступінь дорівнює числу перевірочних символів в циклічному коді, що породжується то звідси випливає, що при непарних число перевірочних символів БЧХ-коду з і довільними не перевищує Припустимо на час, що дорівнює нижній межі мінімальної відстані в коді, тоді отримаємо, що якщо число перевірочних символів і виправляються всі комбінації помилок. Якщо вибрати а примітивним, то довжина блоку в коді дорівнюватиме З (6.7.1) слід, що при або всі комбінації помилок можуть бути виправлені, якщо число перевірочних символів не менше
Так як БЧХ-коди є циклічними кодами, то з результатів § 6.5 слід, що перевірочну матрицю для БЧХ-коду можна обчислити, використовуючи многочлен Перевірочну матрицю можна привести до більш зручної для наших цілей формі, якщо згадати, що є багаточленом, що відповідає кодовому слову тоді і тільки тоді, коли при останньому співвідношення можна переписати у вигляді
Визначаючи перевірочну матрицю як
можна переписати (6.7.4) у вигляді рівності
справедливого і тоді, коли є кодовим словом. Якщо елементам і а при деяких значеннях відповідають однакові мінімальні багаточлени, тоді і тільки тоді, коли при цьому стовпці, відповідні а, можуть бути опущені в (6.7.5). Таким чином, для щойно розглянутого прикладу
Нагадаємо, що згідно з § 6.6 елементи розширення поля можуть розглядатися як -компонентні вектори над Розмноження елемента а з елемент х, що належить відповідає скалярному множенню вектора а на скаляр х з Тому, якщо розглядати елементи Я в (6.7.5) як вектор-рядки в полі то при матричному множенні виробляються лише операції Наприклад, для щойно розглянутого прикладу матриця визначається (6.7.7а), може бути переписана наступним чином (див.рис. 6.6.3):
Теорема 6.7.1. Мінімальна відстань для БЧХ-коду з певним параметром не менше ніж
Доказ. Нехай послідовність символів припустимо, що всі значення цих символів, крім вибираються рівними 0, а інші символи, наприклад
вибираються довільно. Покажемо, що з будь-яких значеннях цілих чисел (задовольняють ), може бути кодовим словом і тоді, коли за цим буде доведено, що це ненульові кодові слова від послідовності, цілком що складається з нулів, щонайменше ніж у позиціях і, отже , мінімальна відстань у коді не менше
При заданому виборі цілих чисел вектор x є кодовим словом і тоді [див. (6.7.4)], коли
Спростимо позначення, визначивши
Тоді співвідношення (6.7.8) листується у вигляді
Ці співвідношення являють собою систему рівнянь [над невідомим Одне рішення даної системи тривіально: Для завершення доказу необхідно показати, що це рішення єдине [з того факту, що не існує іншого рішення, насправді випливає, що не існує іншого рішення в Водночас це рішення єдине, якщо рівняння лінійно незалежні (доказ цього такий самий, як у полі дійсних чисел). Лінійна залежність рівнянь означає, що існує така множина не рівних одночасно нулю елементів поля для яких
Припустимо, що така безліч елементів поля існує, і нехай Співвідношення (6.7.11) виражається таким чином:
Разом з тим є ненульовим багаточленом, ступінь якого не більший (6.7.12) випливає, що кількість коренів не
менше Ці твердження суперечливі і, отже, рівняння лінійно незалежні, що завершує доказ.
Оскільки мінімальна відстань у БЧХ-коді не менша за те, як відомо, будь-яка комбінація з або менших помилок може бути виправлена; Нижче отримаємо алгоритм виправлення всіх таких комбінацій помилок. Насправді цей код здатний виправляти багато комбінацій більш ніж помилок, проте досі невідомий простий алгоритм їх виправлення.
Позначимо через многочлен, що відповідає переданому кодовому слову, через багаточлен, відповідний прийнятої послідовності, а через багаточлен, що відповідає шумовій послідовності. Синдромом назвемо вектор із компонентами
Відзначимо, що кожна з компонент є елементом ввівши матрицю згідно (6.7.5), одержимо Так як є коренем багаточлена то
Тепер припустимо, що під час передачі відбулося деяке фіксоване число помилок, наприклад, на позиціях. Тоді при всіх окрім і (6.7.14) набуває вигляду
Щоб спростити позначення, введемо поняття значень помилок та локаторів помилок, що визначаються співвідношеннями:
Співвідношення (приймає вигляд
Таким чином, Шкодер може обчислити синдром за прийнятою послідовністю у. Якщо декодер може вирішити (6.7.17) і визначити значення помилок та локатори помилок, то він може з (6.7.16) знайти шумову послідовність (Нагадаємо, що N дорівнює мультиплікативному порядку а, то всі елементи різні.) Перейдемо тепер до головне завдання, яке згідно з прийнятою тут схемою полягає у знаходженні рішення (6.7.17).
Насамперед визначимо багаточлен нескінченного ступеня
де за всіх задається співвідношенням
Нагадаємо, що при можна обчислювати безпосередньо за величина невідома, але принаймні визначена для заданої шумової послідовності Можна переписати у вигляді
де через позначений багаточлен нескінченного ступеня Тепер введемо багаточлен таким чином:
Обчислюючи твір правих частин (6.7.20) та (6.7.21), отримуємо
Щоб інтерпретувати цю рівність, корисно запровадити деякі додаткові позначення. Для довільного багаточлена (кінцевого чи нескінченного) нехай визначається співвідношенням
Якщо перевищує ступінь рівний умовимося вважати Позначимо далі
У введених вище позначеннях
Так як члени в ступінь яких більше впливають лише на ті члени многочлена, ступінь яких більше ніж те (6.7.22) отримаємо
Нарешті, зауважимо, що відповідно до рівності (6.7.22), що визначає ступінь не може перевищувати. Тому дужки навколо в (6.7.25) можуть бути опущені і, більше
Зі співвідношення (6.7.26) випливає, що коефіцієнт при у творі а дорівнює 0 для більш детального запису (6.7.26) еквівалентно наступній системі рівностей:
Рівності (6.7.27) дають систему лінійних рівнянь, за якими декодер може знайти невідомих [згідно (6.7.21). для наступних посилань як чотирьох етапів.
Етап 1. Обчислити за прийнятою послідовністю у.
Етап 2. Знайти із (6.7.26) або (6.7.27).
Етап 3. Знайти коріння з таким чином, локатори помилок.
Етап 4. Знайти значення помилок. Зазначимо, що у разі двійкових БЧХ-кодів усі значення помилок дорівнюють 1 (оскільки, за визначенням, вони ненульові) і, отже, етап 4 не потрібен.
Тепер обговоримо докладніше етап 2, а розгляд реалізації інших етапів повернемося трохи пізніше.Зазначимо, що з відшуканні з (6.7.26) декодеру невідомо число помилок Наступна теорема стверджує, що можна однозначно визначено без попереднього знання
Теорема 6.7.2. Припустимо, що сталося помилок та що визначається рівністю (6.7.21). Нехай мінімальне ціле число, для якого існує багаточлен, ступінь якого не перевищує і який задовольняє співвідношенню.
Доказ. Співвідношення можна переписати у вигляді
За визначенням це означає
Рівність (6.7.29) можна розглядати як систему лінійних рівнянь відносне невідомих. (6.7.29) при цих рівняннях з невідомими є лінійно незалежними з тих же причин, які були зазначені під час встановлення лінійної незалежності (6.7.10) у теоремі 6.7.1. Тому єдине рішення цих рівнянь:
Оскільки за величини є корінням многочлена при Бо, по-перше, ступінь не перевищує по-друге, має ті ж коріння, що і, по-третє, то виконується рівність Оскільки ступінь дорівнює ми отримаємо що завершує доказ.
Тепер опишемо дуже простий ітеративний алгоритм знаходження
Ітеративний алгоритм для знаходження.
Відповідно до попередньої теореми, якщо число помилок не перевищує то визначимо через синдромні багаточлени дозволивши рівняння для мінімального і для
багаточлена ступеня, що не перевищує Це завдання найлегше описати в термінах регістру зсуву з лінійним зворотним зв'язком представленого на рис. 6.7.1.
Спочатку в регістрі зберігається послідовність елементів даного поля. Потім регістр обчислює новий елемент через величини зворотних зв'язків відповідно до співвідношення
Числа є елементами того ж поля, що і потім регістр зсувається на одну позицію вправо, після чого зліва в регістр вводиться
Мал. 6.7.1. Регістр зсуву з ліією зворотним зв'язком (PCЛOC).
При кожному з послідовних зрушень праворуч обчислюється новий елемент, що визначається співвідношенням
Назвемо довжиною PCЛOC число розрядів у регістрі зсуву в позначення рис. 6.7.1). Назвемо також многочлен зв'язків РСЛОС многочлен де показані на рис. 6.7.1 величини зворотних зв'язків взяті зі знаком мінус. Оскільки РСЛОС повністю (якщо не вважати спочатку зберігається в ньому послідовність елементів) описується завданням довжини регістру і багаточленом зв'язків, то для позначення PCЛOC з довжиною регістру I і багаточленом зв'язків будемо використовувати назву регістр. Деякі чи всі величини зворотних зв'язків можуть дорівнювати нулю; тому може бути довільним многочленом, ступінь якого не перевищує причому Нарешті, для будь-якого многочлена (кінцевого або нескінченного) будемо говорити, що - регістр генерує тоді і тільки тоді, коли регістр, спочатку зберігав породжує елементи, що залишилися (якщо вони є) методом, що визначається співвідношенням (6.7.32). Оскільки (6.7.32) еквівалентно твердженню, що коефіцієнт при у творі дорівнює 0, то регістр генерує тоді і тільки тоді, коли
Тепер вимальовується зв'язок між пристроєм регістру зсуву з лінійним зворотним зв'язком і завданням знаходження. Завдання полягає у відшуканні такого -регістра з мінімальною довжиною який генерував би. . Буде показано, що це алгоритм працює у разі довільного многочлена над довільним полем. Алгоритм полягає у знаходженні послідовності регістрів, перший з яких є найкоротшим регістром, що генерує другий - найкоротшим регістром, що генерує Регістр, що відтворює алгоритм генерування назвою Грубо кажучи, алгоритм працює наступним чином: при заданому генеруючому перевіряє, чи генерує також виконується
Оскільки за припущенням то питання у тому, чи дорівнює нулю коефіцієнт при у многочлена Ця сума називається наступної різницею, алгоритму; висловлюючи через маємо
Позначимо через коефіцієнт при генерований регістром згідно (6.7.32); тоді отримаємо так що дорівнює різниці між сприятливим значенням наступного вихідного символу і дійсним вихідним символом регістра Якщо алгоритм збільшує на 1, зберігаючи незмінним регістр. Якщо до багаточлена зв'язку додається поправний член, так, щоб правильно генерувалося.
Більш докладний опис алгоритму полягає в наступному: при будь-якому параметри - регістра визначаються через параметри - регістра та параметри апріорного регістру в послідовності де При будь-якому ціле число визначається наступним рекурентним співвідношенням:
де визначаються (6.7.34) або, точніше,
Алгоритм починає роботу з початкових умов
Наступна теорема стверджує, що визначають - регістр і що цей регістр генерує У наступній теоремі буде показано, що - регістр є найкоротшим регістром, що генерує
Теорема 6.7.3. За будь-якого
Твердження а. Згідно з початковими умовами при Доказ негайно випливає з (6.7.35) за допомогою індукції по
Твердження Згідно з початковими умовами Тепер припустимо, що будь-якому заданому Тому що (6.7.36) випливає, що Тому по індукції отримаємо, що при всіх
Твердження Знову скористаємося індукцією згідно з початковими умовами співвідношення (6.7.40) і (6.7.41) виконуються при нехай задано деяке припустимо, що при
Доказ буде завершено, якщо показати, що з цих співвідношень випливає справедливість (6.7.42) і (6.7.43) для Розглянемо окремо випадки. (6.7.43) слід, що
З (6.7.34) отримаємо Тому звідки випливає справедливість (6.7.43) для Тепер припустимо, що Відповідно до (6.7.36) маємо:
де було використано при та потім використано (6.7.37).
Нарешті, з (6.7.36) отримаємо
Мал. 6.7.2. Дії алгоритму в до
Що стосується останнього виразу в (6.7.44), то неважко переконатися, що можна винести за дужки, якщо зменшити одночасно межі на так.
де задля доказу те, що було використано (6.7.37). Підставляючи (6.7.45) та (6.7.46) у (6.7.44), отримуємо що завершує доказ.
Підсумовуючи ці рівності від до і враховуючи, що отримуємо
Враховуючи, що порівняно близькі один до одного, бачимо, що або Взявши рівняння (3) можна вирішити щодо, що дає Отже,
7.7.(а) Нехай прийнята послідовність. Тоді
Декодер вибирає повідомлення 1, якщо ця величина більша за 0 і повідомлення 2 в іншому випадку.
За умови, що повідомлення 1 надіслано, нехай послідовність незалежних гауссівських випадкових величин мають середні та дисперсії Отже, має середню дисперсію
де функція розподілу гауссівської випадкової величини з нульовим середнім та одиничною дисперсією. З симетрії ясно, що і (1) дає можливість помилки.
(б) Імовірність мінімізується вибором таких, які максимізують 2 при обмеженні
Нехай номер каналу з найменшою дисперсією шуму, так що тоді
з рівностями завжди, коли для всіх Отже, для мінімізують ймовірність помилки і
для (см Феллер, т. 1, гл VII, § 1)
(в) З (7.5.57) бачимо, що В - зростаюча функція Я і що при прагненні до 0, В прагне до Отже, з (7.5.58) знаходимо, що
Зауважимо, що цей показник експоненти дорівнює половині показника експоненти, виведеного в пункті Якщо подивитись більш ретельно на зв'язок між швидкістю [див. (7.5.41) і (7.5.60)], то побачимо, що тільки тоді,
Останнє доводить справедливість (6.7.48) у своїй завершує доказ.
З цієї леми випливає, що як функція має вигляд зростаючої послідовності піків; величина для кожного вказує на місцезнаходження попереднього піку, який перевищує будь-який із попередніх піків (ми вважаємо, що в точці є пік, якщо
Перш ніж доводити, що описаний алгоритм за будь-якого призводить до найкоротшого можливого регістру, необхідно навести дві леми.
Лемма 2. Припустимо, що це два регістри, які відповідають співвідношенням
тоді при деякому існує регістр, що задовольняє співвідношенню
Нехай мінімальне ціле число, для якого нехай нехай визначається співвідношенням
Тому є регістром. Підставляючи (6.7.59) в (6.7.58) і помічаючи, можна винести за дужки, якщо одночасно зменшити межі на отримаємо
Оскільки це завершує доказ,
Лемма 3. Припустимо, що при заданих і -реєстр є найкоротшим регістром, що генерує при всіх.
Доказ. Покажемо, що припущення про несправедливість леми призводить до суперечності. Нехай найкоротший регістр, для якого виконуються (6.7.60) і (6.7.61).
Випадок а. Припустимо, що Відомо, що при і тому є найкоротшим регістром, що генерує при Звідси слід, що Тому, оскільки то для регістру виконується рівність
Відповідно до попередньої леми з (6.7.61) і (6.7.62) слідує існування -реєстру, для якого при деякому виконується рівність
Цей регістр коротше, ніж регістр і задовольняє (6.7.60) та (6.7.61). Це суперечить зробленому припущенню.
Випадок Припустимо, що За пропозицією, регістр є найкоротшим регістром, що генерує і тому Отже, в силу (6.7.47),
що суперечить (6.7.60).
Теорема 6.7.4. При будь-якому і всіх немає регістру, який генерує і має довжину, меншу, ніж -регістр, побудований за допомогою описаного вище алгоритму.
Доказ.Проведемо індукцію по Очевидно, що теорема справедлива при Припустимо, що вона виконується для будь-яких заданих і деякого даного. -Тепер припустимо, що так що
Розглянемо який-небудь регістр, що генерує Тоді маємо і згідно з лемою 2 з існування
(Клацніть для перегляду скана)
-Регістрів слідує існування при деякому такого -Регістру для якого
Відповідно до леми Тому тоді -регі;гр не коротше, ніж -регістр, що завершує доказ.
Блок-схема представлена на рис. 6.7.4, автором якої є Мессі (1968), пропонує спосіб реалізації алгоритму. Зазначимо, що співвідношення (6.7.49) використовується тут як критерій для вказівки зміни Довжина регістрів, представлених на рис. 6.7.4, повинна бути достатньою для зберігання багаточлена зв'язків найдовшого очікуваного регістру. Виберемо для декодування БЧХ-кодів і розташуємо крім коефіцієнта зліва. Можна вибрати і цим гарантувати виправлення всіх комбінацій лише помилок. Що стосується двійкових БЧХ-кодів елементи є елементами і з регістрів, представлених на рис. 6.7.4 може бути реалізований за допомогою двійкових регістрів. Пристрій, що виконує множення можна зробити так, як показано на рис. 6.6.5.Легко бачити, що складність обладнання, необхідного для регістрів та помножувачів, пропорційна Також неважко переконатися, що час, необхідний для знаходження пропорційно [або трохи більше, що залежить від способу обчислення Безумовно, при побудові такого пристрою необхідно вирішити велику кількість технічних питань; важливо помітити, однак, що для такого пристрою необхідно разюче мало обладнання і разюче мало обчислювального часу. Берлекемп (1967) також довів, що для двійкових кодів з і при непарних величина завжди дорівнює нулю. Використання цієї обставини по суті вдвічі скорочує обчислювальний час для знаходження На цьому ми закінчимо обговорення другого етапу процедури декодування БЧХ-кодів.
Тепер коротко розглянемо реалізації етапів 1, 3 та 4 для БЧХ-декодера. На етапі 1 можна обчислювати елементи синдрому наступним способом:
Таким чином, можливий шлях обчислення полягає у складанні всіх послідовно прийнятих символів спочатку порожньому регістрі; сума потім повинна бути помножена на і повернена в регістр, що чекає на наступний прийнятий символ.
Етап 3 найлегше реалізувати за допомогою процедури Ченя (1964). Якщо число помилок не перевищує то обчислений на етапі 2 визначається співвідношенням (6.7.21), і помилка
у позиції станеться тоді й тільки тоді, коли або, що те саме, тоді й тільки тоді, коли
Мал. 6.7.5. Крок 3 під час декодування БЧХ-коду: знаходження позицій помилок. Спочатку в регістрі зберігаються Потім проводиться множення та перевірка гіпотези після цього проводиться множення та перевірка гіпотези і так далі до
Остання передбачає використання схеми рис.6.7.5 для реалізації критерію (6.7.63) спочатку для потім і т.п. буд.
Як було зазначено, у разі двійкових БЧХ-кодів етап 4 в процедурі декодування не є необхідним. Тому прийняті символи можуть виходити з декодера синхронно з операціями, виробленими пристроєм на рис. 6.7.5, якщо на виході пристрою просто проводиться додавання по модулю 2 при зміні від до 0, що дозволяє отримати передане кодове слово, якщо відбулося не більше помилок.
Якщо при використанні двійкового коду сталося більш ніж помилок, то може статися одна з наступних трьох подій. По-перше, довжина Л-регістра, який був на етапі 2, могла бути більшою ніж у пристрої на рис. то в цьому випадку не можна знайти, але досить просто виявити цю подію. По-друге, цілком можливо також, що знайдене на етапі 2, не перевищує але не має I коренів. У цьому випадку на етапі 3 буде
зроблено менше, ніж I виправлень, але декодована послідовність не буде кодовим словом. Це знову може бути легко виявлено або шляхом підрахунку числа виправлень, або шляхом перевірки, чи кодова слово декодована послідовність. Нарешті, цілком можливо, що регістр має довжину і що при декодуванні буде знайдено помилок. У цьому випадку декодована послідовність буде кодовим словом, яке відрізняється від прийнятої послідовності більш ніж у позиціях. При цьому не можна виявити помилку декодування, але ми принаймні знаємо, що декодер прийняв у двійковому симетричному каналі рішення максимально правдоподібності.
Звернемося тепер до пошуку значень помилок (етап 4) у процесі декодування недвійкових БЧХ-кодів. Визначимо багаточлен (6.7.22) як
Тоді відповідно визначається таким чином через
Багаточлен можна знайти безпосередньо з (6.7.68) або, що більш красиво, його обчислення можна включити у вигляді складової частини в ітеративний алгоритм знаходження.
де визначаються (6.7.34) і (6.7.35) Для цього в блок-схему на рис. 6.7.4 необхідно включити два додаткові регістри; обчисленні аналогічні операціям, що здійснюються регістрами при обчисленні Доказ того, що за будь-якого майже аналогічно доказ теореми 6.7.3 і це наведено у вигляді задачі 6.35.
Після знаходження неважко переконатися, що згідно (6.7.67)
Можна спростити праву частину (6.7.70), якщо ввести похідну
Легко реалізувати обчислення а якщо є ступенем 2, то дорівнює сумі членів в непарних ступенях, поділеної на так як
то отримаємо (див. задачу 6.36)
Підставляючи (6.7.72) у (6.7.70), отримуємо
Використовуючи визначення дані (6.7.16), отримуємо наступну формулу для знаходження кожного з ненульових шумових символів
Кожна з трьох функцій, що входять у праву частину (6.7.74), може бути послідовно обчислена всім при зміні піт до 0 за допомогою пристрою того ж типу, що і на рис.
На цьому закінчується обговорення декодування БЧХ-кодів. Головний висновок полягає в тому, що за задумом це декодування є складним, воно дуже просто в сенсі часу декодування і необхідної складності обладнання.Якщо не рахувати осередків пам'яті, необхідних для запам'ятовування прийнятого слова, і пристрої обчислення зворотних елементів в кількість необхідного обладнання пропорційно Час декодування на етапі 2 пропорційно а на етапах 3 і 4 пропорційно
Давайте подивимося, що можна сказати про поведінку двійкових БЧХ-кодів у межі при На час припустимо, що є гарною оцінкою для числа перевірочних символів у коді, так що
де швидкість передачі у двійкових символах. Так як при фіксованому R величина повинна прагнути до 0 при прагненні N до нескінченності. Тому кількість помилок, які можна виправити описаним алгоритмом декодування, врешті-решт стає меншою за середню кількість помилок у каналі. Пітерсон (1961) точно обчислив число перевірочних символів у різних двійкових БЧХ-кодах; з його результатів випливає, що за
Разом з тим це зменшення настає при таких великих значеннях, що ця межа мало означає для практики.
Коди Ріда-Соломона (1960) є цікавим приватним класом БЧХ-кодів з параметром рівним 1; інакше кажучи, в цьому випадку розширене поле, в якому визначено так, збігається з полем символів для кодових літер. Тоді мінімальний багаточлен для а дорівнює а, так що маємо
Тому вказаний код має перевірочних символів і мінімальну відстань. відповідне кодове слово матиме не більше ненульових символів.
Так як у коді Ріда-Соломона довжина блоку N дорівнює або дільнику числа, то неважко помітити, що ці коди корисні лише при великих обсягах алфавіту. Їх можна ефективно використовувати в безперервних за часом каналах, де вхідний алфавіт складає безліч сигналів. Форні (1965) ефективно використовував їх у каскадної схемою, де символи коду Ріда-Соломона були кодовими словами меншому внутрішньому коді. Форні показав, що такі коди можна використовувати при швидкостях передачі, як завгодно близьких до пропускної спроможності. Імовірність помилки їм експоненційно зменшується зі зростанням довжини блоку, а складність декодування пропорційна малого ступеня довжини слова. Коди Ріда-Соломона можна безпосередньо використовувати в каналі з малим вхідним алфавітом шляхом представлення кожної літери в кодовому слові у вигляді послідовності літер каналу. Ця техніка корисна для застосування в каналах, де помилки поєднуються в групи, оскільки кількість операцій декодування залежить лише від числа послідовностей вихідних символів каналу, що містять помилки.
Пошук хешів для розшифровки (MD5, SHA1, MySQL, NTLM, SHA256, SHA512 і т.д.)
Введіть ваші хеш тут і ми спробуємо розшифрувати їх безкоштовно.
Що це за інструмент
Hashes.com – сервіс пошуку хешей. Це дозволяє вводити хеші різних алгоритмів: MD5, SHA-1, Vbulletin, Invision Power Board (IPB), MyBB, Bcrypt, Wordpress, SHA-256, SHA-512, MYSQL5 і т.д. І шукати відповідний хеш незахешований текст («знайдено») у нашій базі даних вже знайдених до цього хешів.
Начебто ви маєте свій потужний кластер для пошуку хешей - але з негайними результатами!
Ми будуємо нашу базу даних хешів із серпня 2007 року.
Ми не розшифровуємо ваш хеш у режимі реального часу – ми просто кешуємо важку роботу багатьох ентузіастів упродовж багатьох років.
Алгоритм дайджесту повідомлень MD5 - це 128-бітовий алгоритм хешування, що широко використовується. Хоча MD5 спочатку призначався для використання як криптографічної хеш-функції, було виявлено, що він страждає від великої кількості вразливостей. Його все ще можна використовувати як контрольну суму для перевірки цілісності даних, але тільки від ненавмисного пошкодження даних. Він залишається придатним для інших не криптографічних цілей, наприклад, для визначення розділу для конкретного ключа в розділеній базі даних. Слабкі сторони MD5 були використані в цій сфері, наприклад, сумновідомим шкідливим ПЗ Flame у 2012 році. Інститут розробки програмного забезпечення CMU вважає MD5 по суті криптографічно зламаним та непридатним для подальшого використання. MD5 Розшифровка.
У криптографії SHA-1 (Secure Hash Algorithm 1) - це алгоритм криптографічного хешування. Для вхідного повідомлення алгоритм генерує 160-бітове (20 байт) хеш-значення, зване також дайджестом повідомлення, яке зазвичай відображається як 40-розрядне шістнадцяткове число. розроблений Агентством Національної Безпеки США та є Федеральним Стандарт обробки інформації США. З 2005 року SHA-1 не вважається безпечним від противників, що добре фінансуються, а з 2010 року багато організацій рекомендували його заміну на SHA-2 або SHA-3. Microsoft, Google, Apple та Mozilla оголосили, що їхні відповідні браузери припинять визнавати SSL-сертифікати SHA-1 до 2017 року. Розшифровка SHA1.
Алгоритм хешування MySQL5 реалізує подвійний бінарний алгоритм хешування SHA-1 для користувача пароля. Розшифровка MySQL.
NT (Нова технологія) LAN Manager (Менеджер) (NTLM) - це набір протоколів безпеки Microsoft, який забезпечує автентифікацію, цілісність та конфіденційність для користувачів. NTLM є наступником протоколу автентифікації в Microsoft LAN Manager (LANMAN), старішому продукті Microsoft. Набір протоколів NTLM реалізований в Постачальнику підтримки безпеки Microsoft (SSPI), який поєднує протокол автентифікації LAN Manager, протоколи сеансів NTLMv1, NTLMv2 і NTLM2 в одному пакеті. Використання цих протоколів або їх використання в системі регулюється настройками Групової Політики, для яких різні версії Windows мають різні параметри за промовчанням. Паролі NTLM вважаються слабкими, тому що вони можуть бути легко зламані за допомогою сучасного обладнання. NTLM Розшифровка
SHA-2 (Secure Hash Algorithm 2) є набір криптографічних хеш-функцій, розроблених Агентством Національної Безпеки США (NSA). Вони побудовані на основі структури Меркла-Дамгора (Merkle-Damgård), функції одностороннього стиснення, побудованої з використанням структури Девіса-Мейєра (Davies-Meyer) з (класифікованого) спеціалізованого блокового шифру. SHA-2 включає значні зміни в порівнянні з його попередником, SHA-1. Сімейство SHA-2 складається з шести хеш-функцій з дайджестами (значеннями хеш-функції), які становлять 224, 256, 384 або 512 біт: Алгоритми SHA-224, SHA-256, SHA-384, SHA-512, SHA-5 /224, SHA-512/256. SHA256 Розшифровка.
