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

 
RU Сын советского программиста #14.07.2004 13:24
+
-
edit
 
радиоэлектроника техника
Кто владеет магией кода Рида-Соломона? Помогите, а то у меня от полиномов, синдромов и полей Галуа голова кругом идет :(

Объясните популярно алгоритм исправления ошибок, я спасибо скажу :)
Сын советского программиста  
?? Tosha_443 #15.07.2004 10:43
+
-
edit
 

Tosha_443

втянувшийся
ага, из курса кодирования информации помню одно - формул там страницы на три, мелким почерком :)
Не ошибается тот, кто ничего не делает  
RU ab #16.07.2004 02:41  @Сын советского программиста#14.07.2004 13:24
+
-
edit
 
Объясните популярно алгоритм исправления ошибок, я спасибо скажу :)
[»]
 


популярно это можно понять так. слово разбивается на перекрывающиеся куски. для каждого куска считается контрольная сумма. ошибка будет в точке пересечения двух или более кусков с ошибкой в контрольной сумме у каждого. инвертируем бит в этой точке - исправляем.

вот простой вариант реализации
http://m0l.nm.ru/zaschita_virusov.htm
]Итак, представляем защищаемый блок данных в виде матрицы. По каждому столбцу и каждой строке матрицы считаем контрольную сумму, попросту XORим байты один на другой. Теперь представим, что изменился один байт. Тогда изменятся контрольные суммы соответствующих столбца/строки матрицы, своими номерами указывая
координаты байта.

есть второй подход к описанию. слова выбираются так чтобы они различались минимум на несколько бит - кодовое расстояние между ними болшьшое. тогда при искажении его все равно можно отнести к более похожему на него - исправить.

http://www.bolshe.ru/book/id=410
]кодовым расстоянием данного кода называется минимальное расстояние между двумя любыми словами в этом коде. Если имеется хотя бы одна пара слов, отличающихся друг от друга только в одном разряде, то минимальное расстояние данного кода равно 1. Простой (не избыточный) код имеет минимальное расстояние dmin— 1. Для избыточных кодов dmin] 1. Если dmin]2, то любые два слова в данном коде отличаются не менее чем в двух разрядах, следовательно, любая одиночная ошибка приведет к появлению запрещенного слова и может быть обнаружена. Если dmin=3, то любая одиночная ошибка создает запрещенное слово, отличающееся от правильного в одном разряде, а от любого другого разрешенного слова — в двух разрядах. Заменяя запрещенное слово ближайшим к нему (в смысле кодового расстояния) разрешенным словом, можно исправить одиночную ошибку.

для понимания невредно начать с начала - с кодов Хэмминга, они самые простые
http://www.computer-museum.ru/galglory/hamming.htm
 
RU Клапауций #16.07.2004 10:23
+
-
edit
 

Клапауций

координатор
★★☆
Интересно, а у Рида-Соломона какое минимальное кодовое расстояние ?
В тот день, когда ты решишь, что ты лишен недостатков , попробуй прогуляться по воде  
RU Сын советского программиста #17.07.2004 13:01  @Клапауций#16.07.2004 10:23
+
-
edit
 
Интересно, а у Рида-Соломона какое минимальное кодовое расстояние ?
[»]
 


d = n - k + 1, где
d - минимальное кодовое расстояние
n - длина кода
k - длина информации
Сын советского программиста  
RU Сын советского программиста #17.07.2004 13:13
+
-
edit
 
ab, спасибо, хоть алгоритм исправления ошибок RS-кодом не объяснили :)
В кодах Хеминга я разобрался, еще на той неделе :) А вот коды Рида-Соломона на порядок сложнее, а освоить нужно быстро :wacko:

ЗЫ
Ваша первая ссылка... эээ... не совсем RS-код, точнее совсем не RS-код :)
Сын советского программиста  
RU Сын советского программиста #17.07.2004 13:27
+
-
edit
 
Наковырял цикл статей Криса Касперского в журнале Системный администратор по коду Рида-Соломона. Написано простым доступным языком, с примерами на С. Я получил настоящее удовольствие, особенно от второй части.

Могущество кодов Рида-Соломона или Информация, воскресшая из пепла
Полиномиальная арифметика и поля Галуа или Информация, воскресшая из пепла II
Полиномиальная арифметика и поля Галуа или Информация, воскресшая из пепла III
Сын советского программиста  
ab, спасибо, хоть алгоритм исправления ошибок RS-кодом не объяснили :)
 


так все блочные коды в принципе декодируются абсолютно одинаково т.е. перебираются все допустимые кодовые комбинации и сравниваются с реально принятой. выбирается та из допустимых, для которой различие между ней и принятой (Хэмминговское расстояние) минимально.

другое дело что многим хочется побыстрее. ну так это уже частности.
 
RU Сын советского программиста #18.07.2004 10:46  @ab#18.07.2004 02:50
+
-
edit
 
другое дело что многим хочется побыстрее. ну так это уже частности.
[»]
 


Ну так нужно в PIC запихнуть ;)
Сын советского программиста  
RU ab #18.07.2004 18:58  @Сын советского программиста#18.07.2004 10:46
+
-
edit
 
Ну так нужно в PIC запихнуть ;)
[»]
 


а вот это не смотрел?

http://dsp-book.narod.ru/RS255253.ZIP

 
RU Сын советского программиста #18.07.2004 21:27
+
-
edit
 
ab, спасибо за исходник. Теперь немного оптимизирую, как написано у Касперского, и сойдет за первый вариант. :)

Вообще хотелось бы исправить больше одной ошибки. Но пока туго доходит как, несколько непривычна арифметика в полях Галуа. ;)

Сын советского программиста  
+
-
edit
 

dmitmal

новичок
Народ, кто разобрался как исправить больше одной ошибки при помощи кодов Рида-Соломона??? Помогите, очень нужно, плиз!!
 
MD Wyvern-2 #14.04.2009 15:18  @Сын советского программиста#18.07.2004 21:27
+
-
edit
 

Wyvern-2

координатор
★★★★★
С.с.п.> .... Но пока туго доходит как, несколько непривычна арифметика в полях Галуа. ;)

[Немного флейма :) ]

Эварист Галуа ( Галуа, Эварист — Википедия ) - основатель современной алгебры. И не только мой любимый математик, но и формально считается самым великим и гениальным ученым в истории Человечества.
Это данные полученные при небольшом исследовании группы энтузиастов-математиков Гарварда. Суть исследования была проста: индекс цитирования работ ученых разделили на общий объем этих работ... И малюсенькая, в несколько страниц объемом, работа Эвариста Галуа, написанная им по легенде в ночь перед дуэлью, на которой он был убит в возрасте всего 21 года, оказалась впереди всех работ с огромным отрывом...

И не надо бояться, что работы Галуа слегка ...мнээээ....заумны. В конце концов это работы реального гения. Да и компания у вас, непонимающих, что надо:
_________________________________________________
а 20 лет жизни Галуа успел сделать открытия, ставящие его на уровень крупнейших математиков XIX века. Решая задачи по теории алгебраических уравнений, он заложил основы современной алгебры, вышел на такие фундаментальные понятия, как группа (Галуа первым использовал этот термин, активно изучая симметрические группы) и поле (конечные поля носят название полей Галуа).

Галуа исследовал старую проблему, решение которой с XVI века не давалась лучшим математикам: найти общее решение уравнения произвольной степени, то есть выразить его корни через коэффициенты, используя только арифметические действия и радикалы.
Работы Галуа, немногочисленные и написанные сжато, поначалу остались непоняты современниками. Огюст Шевалье и младший брат Галуа, Альфред, послали последние работы Галуа Гауссу и Якоби, но ответа не дождались[1].
Статья, посланная Пуассону, отвергнута со следующей резолюцией [2]:

Во всяком случае, мы сделали все от нас зависящее, чтобы понять доказательство г-на Галуа. Его рассуждения не обладают ни достаточной ясностью, ни достаточной полнотой для того, чтобы мы могли судить об их точности, поэтому мы не в состоянии дать о них представление в этом докладе

Только в 1843 году открытия Галуа заинтересовали Лиувилля, который опубликовал и прокомментировал их (1846).

Открытия Галуа произвели огромное впечатление и положили начало новому направлению — теории абстрактных алгебраических структур. Следующие 20 лет Кэли и Жордан развивали и обобщали идеи Галуа, которые совершенно преобразили облик всей математики.
_________________________________________________
:)
[Флейм окончен]
Жизнь коротка, путь искусства долог, удобный случай мимолетен, опыт обманчив.... Ἱπποκράτης  3.0.83.0.8
+
-
edit
 

dmitmal

новичок
История - это конечно хорошо :), но все-таки! Я уже весь инет перерыл и не могу найти ни одной стоящей программы... Кто с этим разбирался, отзовись!
 
+
-
edit
 

Mishka

модератор
★★★
dmitmal> История - это конечно хорошо :), но все-таки! Я уже весь инет перерыл и не могу найти ни одной стоящей программы... Кто с этим разбирался, отзовись!

А этого — Журнал "Системный Администратор" - электронный вариант - 2003 - AV5 — не хватает?
 6.06.0
+
-
edit
 
+
-
edit
 

Mishka

модератор
★★★
Forward Error Correcting Codes — ещё программки. Если охота по программкам разбираться.
 6.06.0
+
-
edit
 

dmitmal

новичок
Спасибо большое за материал! На самом деле мне программа и нужна была :)
Скачал одну библиотеку rscode-1.0.tar.gz (там как раз то что мне нужно), только чем ее под виндой откомпилить не знаю. Может кто в курсе? Содержит файлы *.c, *.h и Makefile.
 
+
-
edit
 

HolyBoy

аксакал

dmitmal> Скачал одну библиотеку rscode-1.0.tar.gz (там как раз то что мне нужно), только чем ее под виндой откомпилить не знаю. Может кто в курсе? Содержит файлы *.c, *.h и Makefile.

Судя по *.c — это надо компилировать компилятором С, а судя по расширению архива и его содержимому, сей конкретный компилятор наверняка gcc, ибо скорее всего эта библиотека для использования в линуксе написана. Так что учтите, под виндой возможно не заведётся. ;)
 
+
-
edit
 

Mishka

модератор
★★★
dmitmal>> Скачал одну библиотеку rscode-1.0.tar.gz (там как раз то что мне нужно), только чем ее под виндой откомпилить не знаю. Может кто в курсе? Содержит файлы *.c, *.h и Makefile.
HolyBoy> Судя по *.c — это надо компилировать компилятором С, а судя по расширению архива и его содержимому, сей конкретный компилятор наверняка gcc, ибо скорее всего эта библиотека для использования в линуксе написана. Так что учтите, под виндой возможно не заведётся. ;)

Дык, там же не системная библиотека. Ну и всякие среды эммуляции есть. :) Но после того, как товарищ заявил, что ему и нужна была программа, т.е. разбираться он и не собирается — я умываю руки. Вот такой я сноб на Авиабазе. :F Пусть сам и делает.
 6.06.0
EE Татарин #21.04.2009 18:54  @HolyBoy#21.04.2009 16:39
+
-
edit
 

Татарин

координатор
★★★★☆
HolyBoy> Судя по *.c — это надо компилировать компилятором С, а судя по расширению архива и его содержимому, сей конкретный компилятор наверняка gcc, ибо скорее всего эта библиотека для использования в линуксе написана. Так что учтите, под виндой возможно не заведётся. ;)
Да там POSIX, насколько я посмотрел. А если и не заведётся, то править немного.
...А неубитые медведи делили чьи-то шкуры с шумом. Боюсь, мы поздно осознали, к чему всё это приведёт.  1.0.154.531.0.154.53

pokos

аксакал

Mishka> ...Но после того, как товарищ заявил, что ему и нужна была программа, т.е. разбираться он и не собирается — я умываю руки. ...
Да, Мишаня, да. Студенты всё больше становятся похожими на ПТУшников. Разбираться уже нах никому не надо, есть же готовое! А "старички" подскажут, где взять.
"До чего довёл планету этот фигляр ПэЖэ..."
 6.06.0
RU Алдан-3 #22.04.2009 12:39  @pokos#22.04.2009 12:22
+
-
edit
 

Алдан-3

аксакал
★★☆
pokos> Да, Мишаня, да. Студенты всё больше становятся похожими на ПТУшников

"Пойми, заказчику не важно как мы сделаем работу, ему важно когда мы её сделаем!"

Хм, вот. Из реального диалога с.

Так что похожие на ПТУшников студенты — увы, норма.

Им тоже когда сделать важнее чем как, поэтому берём максимум уже готовых кусков и тяп-ляп склеиваем их в что то похожее на требования заказчика (преподавателя).
Особенно его раздражало то, что его постоянно спрашивали, чем он так раздражен.  3.0.83.0.8
CA pokos #22.04.2009 12:44  @Алдан-3#22.04.2009 12:39
+
-
edit
 

pokos

аксакал

Алдан-3> Им тоже когда сделать важнее чем как, поэтому берём максимум уже готовых кусков и тяп-ляп склеиваем их в что то похожее на требования заказчика (преподавателя).
Я тебе так скажу. Когда у тебя первый заказчик, такая схема работает. Херово, но работает. Когда у тебя заказчик 10-й, то нужно уже не из чужих кусков лепить, а из своих. Оно быстрее и дешевле получается.
А у студентов просто все заказчики - первые.
 6.06.0
RU Алдан-3 #22.04.2009 13:23  @pokos#22.04.2009 12:44
+
-
edit
 

Алдан-3

аксакал
★★☆
pokos> нужно уже не из чужих кусков лепить, а из своих.

Понимаете в чём дело. Вы говорите как нужно. А я как есть :)

Ну вот так оно у нас работает в наших краях.
Особенно его раздражало то, что его постоянно спрашивали, чем он так раздражен.  3.0.83.0.8

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru