Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 32
Спасибо за статью! К сожалению, в интернете очень сложно найти понятные материалы про коды Рида-Соломона на русском языке. Ваша же статья понравилась выделением цветами «переносящихся» чисел, ссылками, а также достаточно понятным изложением с помощью простого примера.
Кстати стоит добавить, что также, именно благодаря кодам Рида-Соломона, читаются большинство матричных штрихкодов (такие, как QR Code, Datamatrix и прочие). А также позволяет делать внутри них рисунки, сохраняя возможность правильного распознавания.
Кстати стоит добавить, что также, именно благодаря кодам Рида-Соломона, читаются большинство матричных штрихкодов (такие, как QR Code, Datamatrix и прочие). А также позволяет делать внутри них рисунки, сохраняя возможность правильного распознавания.
Прочитал сначала как «Коты Рида-Соломона» из-за картинки :)
С кодами РС знаком, почти весь семестр занимался ими + летняя практика.
Возможно лекции были очень хорошие и я все относительно быстро освоил. Но эта статья меня только испугала наличием абсолютно незнакомых названий и методов (вполне возможно, что все они носят несколько названий или применяются в разных задачах (теория и практика => разные подходы). Например, процедура Ченя у нас была для поиска позиции ошибки), поэтому я и не знаю как реагировать на статью.
Но все равно спасибо, русскоязычной и наглядной информации действительно мало в интернете.
С кодами РС знаком, почти весь семестр занимался ими + летняя практика.
Возможно лекции были очень хорошие и я все относительно быстро освоил. Но эта статья меня только испугала наличием абсолютно незнакомых названий и методов (вполне возможно, что все они носят несколько названий или применяются в разных задачах (теория и практика => разные подходы). Например, процедура Ченя у нас была для поиска позиции ошибки), поэтому я и не знаю как реагировать на статью.
Но все равно спасибо, русскоязычной и наглядной информации действительно мало в интернете.
Коты, однозначно! Картинка провокационная. :)
Там в alt'е изображения даже написано, кому котэ принадлежит :)
Методов сейчас много, мы изучали (скорее всего, вы тоже) по два-три алгоритма для каждого этапа, я выбрал те, которые объяснялись наиболее подробно. Кстати, алгоритм Берлекампа-Месси — это первый открытый алгоритм поиска позиции ошибки, после его открытия коды Рида-Соломона получили возможность применяться на практике.
Например, процедура Ченя у нас была для поиска позиции ошибки
Методов сейчас много, мы изучали (скорее всего, вы тоже) по два-три алгоритма для каждого этапа, я выбрал те, которые объяснялись наиболее подробно. Кстати, алгоритм Берлекампа-Месси — это первый открытый алгоритм поиска позиции ошибки, после его открытия коды Рида-Соломона получили возможность применяться на практике.
Да вроде нет, нам может быть про них говорили, а в итоге рассказывали что-то общее, ну или я про что-то другое пропустил мимо ушей.
Общий алгоритм у нас был примерно такой:
1. Находим порождающим полином g(x) на основе параметра l0
2. Брали m(x) какое-нибудь — сообщение
3. Затем находили c(x) * xr mod g(x)
4. Находили кодовое слово a(x) = m(x) * xr + c(x)
5. Делали в кодовом слове 2 или 1 ошибку, т.е. y(x) = a(x) + e(x)
6. Затем находили синдромы S1-S4
7. Находим через синдромы локаторы ошибок
8. Через локаторы ошибок находим позиции ошибок
9. Затем через манипуляции с матрицами из синдромов находим величины ошибок на позициях из шага 8
10. Складываем коэф из y(x) с величинами ошибок из шага 9 на позициях из шага 8
11. PROFIT!
При условии постоянной практики, подобные задачи решались минут за 30, а иногда и на скорость, чтобы получить халявные баллы в общий зачет по предмету.
Причем вся математика сводилась к сумме степеней элементов из поля галуа или же сумме бинарных векторов + работа с матрицами. Все. Поэтому смотреть на эти вот преобразования фурье мне страшно.
Общий алгоритм у нас был примерно такой:
1. Находим порождающим полином g(x) на основе параметра l0
2. Брали m(x) какое-нибудь — сообщение
3. Затем находили c(x) * xr mod g(x)
4. Находили кодовое слово a(x) = m(x) * xr + c(x)
5. Делали в кодовом слове 2 или 1 ошибку, т.е. y(x) = a(x) + e(x)
6. Затем находили синдромы S1-S4
7. Находим через синдромы локаторы ошибок
8. Через локаторы ошибок находим позиции ошибок
9. Затем через манипуляции с матрицами из синдромов находим величины ошибок на позициях из шага 8
10. Складываем коэф из y(x) с величинами ошибок из шага 9 на позициях из шага 8
11. PROFIT!
При условии постоянной практики, подобные задачи решались минут за 30, а иногда и на скорость, чтобы получить халявные баллы в общий зачет по предмету.
Причем вся математика сводилась к сумме степеней элементов из поля галуа или же сумме бинарных векторов + работа с матрицами. Все. Поэтому смотреть на эти вот преобразования фурье мне страшно.
глянул в лекции. у нас был Алгоритм Питерсона — Горенстейна — Цирлера (ПГЦ).
Мы тоже изучали метод с порождающим полиномом g(x), при этом он у нас выводился из формулы прямого дискретного преобразования Фурье.
Вообще, все коды Рида-Соломона имеют в основе дискретное преобразование Фурье.
Ваш алгоритм похож на тот, который мы изучали.
Методы, которые у нас были по кодированию: 1) чистое DFT; 2) несистематическое годирование с g(x); 3)систематическое кодирование с g(x) и вычислением остатка; 4) систематическое кодирование с полиномом парности.
Методы по нахождению позиции ошибки: 1) метод с помощью построения кривых Prony; 2) Берлекамп-Месси; 3) метод эвклидового деления в двух разновидностях.
Методы по нахождению значений ошибок: 1) рекурсивный метод; 2)метод Форни
Вообще, все коды Рида-Соломона имеют в основе дискретное преобразование Фурье.
Ваш алгоритм похож на тот, который мы изучали.
Методы, которые у нас были по кодированию: 1) чистое DFT; 2) несистематическое годирование с g(x); 3)систематическое кодирование с g(x) и вычислением остатка; 4) систематическое кодирование с полиномом парности.
Методы по нахождению позиции ошибки: 1) метод с помощью построения кривых Prony; 2) Берлекамп-Месси; 3) метод эвклидового деления в двух разновидностях.
Методы по нахождению значений ошибок: 1) рекурсивный метод; 2)метод Форни
С Фурье почему немного не так. Бесконечный периодический сигнал раскладывается в ряд Фурье(конечное количество синусоид), а конечный сигнал переходит в частотную область при помощи интеграла Фурье, и представляет из себя не ряд а спектральную плотность, что по сути является бесконечным количеством синусоид.
Плюс еще одна поправка — в частотной области функция комплексная, а не вещественная. Иными словами, «зная список частот», мы сигнал не восстановим — нам нужен еще и список фаз.
Да, вы правы, однако то предложение служило лишь целью описать примерно. Нет особой нужды использовать преобразование Фурье для периодического сигнала, поэтому по умолчанию я имел в виду непериодический сигнал, который несет какую-то информацию. Что касается бесконечного числа синусоид, следующего из спектральной плотности: это бы лишь усложнило понимание концепции для читающего. По ссылке, приведенной в том же абзаце, автор также объясняет на примере конечного числа синусоид. К тому же, далее у нас рассматривается именно дискретное преобразование, что даст на выходе конечный набор значений.
Возможно, есть смысл расписать преобразование Фурье для сигналов более подробно, и вместе с тем несложно, подумаю над этим.
Возможно, есть смысл расписать преобразование Фурье для сигналов более подробно, и вместе с тем несложно, подумаю над этим.
Сложение: 1+2=3; 4+5=2. В общем, результаты всегда xor’ятся.Простите, но что и с чем здесь поксорилось? Больше похоже на сложение по модулю.
Вычитание, умножение – так же.Что — «так же»? Сложение — xor, и умножение — xor? Не может такого быть. Дали бы хоть ссылку на Википедию, если не получается объяснить понятными словами.
Кстати, то, что вы привели — это поле Zn, известное так же как поле вычетов. А в кодах Рида-Соломона используются более общий вариант полей Галуа — поля полиномов над Zn.
Больше похоже на сложение по модулю.
Вы правы, это сложение по модулю. Исправил, также расписал более подробно арифметические операции.
А в кодах Рида-Соломона используются более общий вариант полей Галуа — поля полиномов над Zn.
Поле полиномов над Zn используется в расширенных кодах Рида-Соломона, у меня рассмотрены просто коды Рида-Соломона.
> Количество чисел в поле должно являться простым числом.
Не обязательно. Число элементов конечного поля может быть любой положительной степенью любого простого числа.
Не обязательно. Число элементов конечного поля может быть любой положительной степенью любого простого числа.
Не обязательно. Число элементов конечного поля может быть любой положительной степенью любого простого числа.
Вы описываете расширенные коды Рида-Соломона, где оперируют полиномами над конечным полем. Для рассмотренных в статье кодов Рида-Соломона могут быть использованы только поля с размерностями из простых чисел, как было указано. Основное отличие между расширенными и простыми кодами: в простых используется примитивный элемент, в расширенных — примитивный полином.
Я думал, что поле — это тогда и только тогда, если кол-во элементов — простое число.
Например 4=2^2, множество { 0, 1, 2, 3 } не поле, потому что 2*2=0, как и 2*0=0 и операция деления неоднозначна (0/2=0, 0/2=2).
Например 4=2^2, множество { 0, 1, 2, 3 } не поле, потому что 2*2=0, как и 2*0=0 и операция деления неоднозначна (0/2=0, 0/2=2).
В полях с p^q элементами, q > 1, умножение это не «обычное» умножение по модулю p, оно устроено несколько сложнее.
А, почитал вики. Для умножения 2*2 кодируем { 0, 1, 2, 3 } через { 0, 1, x, x+1 },
тогда x*x=x+1 (по модулю x+1), декодируем обратно в 3.
Если такие трюки разрешены, зачем останавливаться на многочленах одной переменной.
Кто знает, может, кодируя многочленами от x и y, у нас в поле будет не p^k, а другое число элементов.
тогда x*x=x+1 (по модулю x+1), декодируем обратно в 3.
Если такие трюки разрешены, зачем останавливаться на многочленах одной переменной.
Кто знает, может, кодируя многочленами от x и y, у нас в поле будет не p^k, а другое число элементов.
Я знаю — все равно будет p^k. Азы комбинаторики… Кроме того, есть еще и теорема, говорящая о том, что кроме как p^k элементов в конечном поле получить просто невозможно.
Считаем… Поле Z2, макс. степень 2
0, 1, x, y, x+1, y+1, xy, xy+1
8 элементов. Что-ж, контрпример не удался. Придётся согласиться ))
0, 1, x, y, x+1, y+1, xy, xy+1
8 элементов. Что-ж, контрпример не удался. Придётся согласиться ))
И правда, коэф. при любом слагаемом пробегает от 0 до p-1, всего k слагаемых.
Итого, p^k многочленов.
Пример для двух переменных с коэф. из Z3
Итого, p^k многочленов.
Пример для двух переменных с коэф. из Z3
Доказательство очень простое. Пусть поле F состоит из N элементов. Его характеристика (https://en.wikipedia.org/wiki/Characteristic_(algebra)) не может быть 0, т.к. поле конечно. Значит характеристика это простое число p. Значит F содержит подполе Z/pZ из p элементов. Рассмотрим F как векторное пространство над полем скаляров Z/pZ. Его размерность конечна, т.к. F конечно. Пусть размерность равна n. Тогда всякий элемент F однозначно представляется координатами (f1, f2, ..., fn), где fi принадлежит Z/pZ. Значит в F всего имеется ровно p^n элементов.
Да, кольцо вычетов Zp является полем только при простом p. Но не забывайте, что существуют еще и кольца полиномов Zp[x]/fk(x), которые также являются полями при простом p и неприводимом fk(x). Число элементов такого поля как раз и есть pk
Это всё хорошо, но царапины на дисках ни черта не читаются…
Еще у Криса Касперского была хорошая статья про это.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Коды Рида-Соломона. Простой пример