Код Ріда-Соломона

Код Рі́да — Соломо́на (англ. Reed-Solomon codes) — недвійкові циклічні коди, що дозволяють виправляти помилки в блоках даних. Елементами кодового вектора є не біти, а групи бітів (блоки). Дуже поширені коди Ріда — Соломона, що працюють з байтами (октет).

Код Ріда — Соломона є окремим випадком БЧХ-коду.

В даний час широко використовується в системах відновлення даних з компакт-дисків, при створенні архівів з інформацією для відновлення у випадку ушкоджень, в завадостійкому кодуванні.

Історія

Код Ріда — Соломона був винайдений в 1960 році співробітниками лабораторії Лінкольна Массачуссетского технологічного інституту Ірвіном С. Рідом і Густавом Соломоном. Ідея використання цього коду була представлена в статті «Polynomial Codes over Certain Finite Fields». Перше застосування код Ріда — Соломона отримав в 1982 році в серійному випуску компакт-дисків. Ефективні алгоритми декодування були запропоновані у 1969 році Елвіном Берлекемпом (Elwyn Berlekamp) і Джеймсом Мессі () і в 1977 році Давидом Мандельбаумом (метод, що використовує алгоритм Евкліда).

Відразу після появи (1960-ті роки) коди Ріда — Соломона (Р-С) стали застосовуватися як зовнішні коди в каскадних конструкціях, що використовуються в супутниковому зв'язку. У подібних конструкціях q-ті символи Р-С (їх може бути декілька) кодуються внутрішніми згортковими кодами. На приймальному кінці ці символи декодуються м'яким (алгоритмом Вітербі) (ефективний в каналах з білим шумом). Такий декодер буде виправляти поодинокі помилки в q-тих символах, коли ж виникнуть пакетні помилки і деякі пакети q-тих символів будуть декодовані неправильно, тоді зовнішній декодер Ріда — Соломона виправить пакети цих помилок. Таким чином буде досягнута необхідна надійність передачі інформації.

На даний момент коди Ріда — Соломона мають дуже широку сферу застосування завдяки їх здатності знаходити та виправляти багатократні пакети помилок.

Запис і зберігання інформації

Код Ріда — Соломона використовується при запису і зчитуванні в контролерах оперативної пам'яті, при архівуванні даних, запису інформації на жорсткі диски (ECC-пам'ять), запису на CD / DVD диски. Навіть якщо пошкоджено значний обсяг інформації, зіпсовано кілька секторів дискового носія, то коди Ріда — Соломона дозволяють відновити велику частину втраченої інформації. Також використовується при запису на такі носії, як магнітні стрічки і штрихкоди.

Бездротовий і мобільний зв'язок

Цей алгоритм кодування використовується при передачі даних по мережах WiMAX, в оптичних лініях зв'язку, у супутниковому та радіорелейному зв'язку. Метод прямої корекції помилок в трафіку (Forward Error Correction, FEC) ґрунтується на кодах Ріда — Соломона.

Див. також

• (Коди Хеммінга)
• Виявлення та виправлення помилок

Примітки

Посилання

• Могутність кодів Ріда-Соломона, або Інформація, яка воскресла з попелу [ 27 Травня 2014 у Wayback Machine.](рос.)