Comments 31
Pid_maxsim ! {message, self(), <<"Поля Галуа - хочу продолжения. ">>},
receive
{Pid_maxsim, article, PoleGaluaPart2} -> read(PoleGaluaPart2)
end.
Была идея затронуть следующие темы:
1) Коды Рида-Соломона. Теория
2) Арифметика полей Галуа. Теория и реализация
3) Коды Рида-Соломона. Реализации
4) Коды Рида-Соломона. Программные оптимизации
5) Коды Рида-Соломона. Аппаратные оптимизации
Посмотрим, на что хватит времени…
1) Коды Рида-Соломона. Теория
2) Арифметика полей Галуа. Теория и реализация
3) Коды Рида-Соломона. Реализации
4) Коды Рида-Соломона. Программные оптимизации
5) Коды Рида-Соломона. Аппаратные оптимизации
Посмотрим, на что хватит времени…
Прочитав первое слово было подумал, что какого-то Максима хотите обозвать нехорошим словом :D
Аккуратнее надо…
Аккуратнее надо…
«Вычеркнем из порождающей матрицы строки, соответствующие «пропавшим» данным.» — В реальной ситуации еще нужно выяснить какие данные пропали A и B или C и X0…
Если данные, соответствующие каждой буковке, пишутся на свой диск, то выяснение этого вопроса тривиально, нет?
Ну, алгоритм универсальный же.
Используется не только для восстановления данных в системах хранения информации, но и для коррекции ошибок при передаче данных.
А во входящем потоке у нас A-B-C-X0-X1 идут подряд. и тут либо добавлять еще избыточную информацию, чтобы разделить их, либо — поиск ошибок, Форни итп.
Используется не только для восстановления данных в системах хранения информации, но и для коррекции ошибок при передаче данных.
А во входящем потоке у нас A-B-C-X0-X1 идут подряд. и тут либо добавлять еще избыточную информацию, чтобы разделить их, либо — поиск ошибок, Форни итп.
Вообще там есть разделение на стирания (когда приёмник уверен что конкретный бит пропал при передаче) и ошибки (когда приёмник уверен что конкретный бит — вот такой, а на самом деле он был противоположный). Способность кода исправлять что-либо зависит от его расстояния. К примеру код Хэмминга (7, 4) имеет расстояние 3 и способен исправить один бит (при отсутствии стираний), либо два стирания (предполагая что ошибок нет). Если к нему добавить доп. бит контроля чётности, то расстояние увеличится до 4 и код будет способен исправлять одновременно одну ошибку и восстанавливать одно стирание (к примеру если пропал тот самый бит чётности, то код может исправить ошибку в первых 7 битах и восстановить стёртый бит чётности).
Да, в реальных СХД хранится информация о том, какие фрагменты присутствуют на каждом диске. При выходе диска из строя, система составляет список потерянных фрагментов и передаёт эту информацию модулю восстановления данных.
Написано очень хорошо и понятно, спасибо. Продолжения жажду.
Можете что-нибудь сказать о соответствии некоторой матрицы Коши порождающему полиному согласно определения кода Рида-Соломона? Насколько я помню, полиному соответствует некоторая матрица Вандермонда. Спасибо.
Спасибо!
Отличное изложение, понял как 2*2.
Жду продолжения.
Отличное изложение, понял как 2*2.
Жду продолжения.
Спасибо за статью!
В свою очередь хотел бы поделиться кратким списком литературы, а также парой ссылок — для тех, кто желает всесторонне изучить вопросы, связанные с алгебраической теорией кодирования.
Вероятно, книги уже неоднократно упоминались в статьях и комментариях по тематике, однако, на мой взгляд, список литературы никогда не бывает избыточным :)
Из закладок
— «Алгебраическая теория кодирования», Берлекэмп Э., 1971.
— «Теория кодов, исправляющих ошибки», Мак-Вильямс Ф., Слоэн Н.Дж., 1979.
— «Теория и практика кодов, контролирующих ошибки.», 1986.
— «Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение», Морелос-Сарагоса Р., 2005.
— «Кодирование с исправлением ошибок в системах цифровой связи», Кларк Дж., Кейн Дж., 1987.
— «Упаковки шаров, решетки и группы.», Конвей Дж.Н., Слоэн Н.Дж.А., 1990.
Книгу «Упаковка шаров, решетки и группы» сам прочёл относительно недавно — очень понравилось!
— «Введение в алгебраические коды» — лекции преподавателя МФТИ Юрия Львовича Сагаловича, оформленные в виде книги.
— «Коды Рида-Соломона с точки зрения обывателя» — написано простым языком.
— «Коды, исправляющие ошибки» — кратко, понятно и с картинками :)
В свою очередь хотел бы поделиться кратким списком литературы, а также парой ссылок — для тех, кто желает всесторонне изучить вопросы, связанные с алгебраической теорией кодирования.
Вероятно, книги уже неоднократно упоминались в статьях и комментариях по тематике, однако, на мой взгляд, список литературы никогда не бывает избыточным :)
Из закладок
— «Алгебраическая теория кодирования», Берлекэмп Э., 1971.
— «Теория кодов, исправляющих ошибки», Мак-Вильямс Ф., Слоэн Н.Дж., 1979.
— «Теория и практика кодов, контролирующих ошибки.», 1986.
— «Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение», Морелос-Сарагоса Р., 2005.
— «Кодирование с исправлением ошибок в системах цифровой связи», Кларк Дж., Кейн Дж., 1987.
— «Упаковки шаров, решетки и группы.», Конвей Дж.Н., Слоэн Н.Дж.А., 1990.
Книгу «Упаковка шаров, решетки и группы» сам прочёл относительно недавно — очень понравилось!
— «Введение в алгебраические коды» — лекции преподавателя МФТИ Юрия Львовича Сагаловича, оформленные в виде книги.
— «Коды Рида-Соломона с точки зрения обывателя» — написано простым языком.
— «Коды, исправляющие ошибки» — кратко, понятно и с картинками :)
Спасибо за полезную подборку! Если не возражаете, можем добавить в конец самого поста (конечно, с упоминанием вас), чтобы больше людей увидели.
Нет, не возражаю. Рад, что список литературы показался Вам полезным.
Добавьте, пожалуйста, ещё один документ: «Заметки по теории кодирования», А. Ромащенко, А. Румянцев, А. Шень, 2011 год. — своего рода «шпаргалка» — кратко, ёмко, однако требует некоторого уровня подготовки.
Также нельзя обойти стороной семинары по «Теории кодирования», которые регулярно организуются сотрудниками «Институт проблем передачи информации им. А.А. Харкевича Российской академии наук», г. Москва. Ссылка на math-net.ru Далее — по ссылкам — можно найти много интересного по темам, связанным с математической теорией кодирования, поднимаются актуальные вопросы в рамках дисциплины. Например, про последовательное декодирование полярных и расширенных кодов Рида-Соломона.В поисковых же системах можно найти уже статьи автора.
Добавьте, пожалуйста, ещё один документ: «Заметки по теории кодирования», А. Ромащенко, А. Румянцев, А. Шень, 2011 год. — своего рода «шпаргалка» — кратко, ёмко, однако требует некоторого уровня подготовки.
Также нельзя обойти стороной семинары по «Теории кодирования», которые регулярно организуются сотрудниками «Институт проблем передачи информации им. А.А. Харкевича Российской академии наук», г. Москва. Ссылка на math-net.ru Далее — по ссылкам — можно найти много интересного по темам, связанным с математической теорией кодирования, поднимаются актуальные вопросы в рамках дисциплины. Например, про последовательное декодирование полярных и расширенных кодов Рида-Соломона.В поисковых же системах можно найти уже статьи автора.
У покойного Криса Касперски было довольно интересное введение в предмет — «Могущество кодов Рида-Соломона или информация, воскресшая из пепла» — как всегда у автора, статья спорная и отражающая частично его собственный опыт. На данный момент статья доступна в архиве, требует гуглокапчу:
archive.li/SBMti
archive.li/SBMti
UFO just landed and posted this here
Нет. И на всякий случай — мы не Рид и Соломон. Мы YADRO.
UFO just landed and posted this here
Это уже обсуждалось в комментах к самой первой нашей статье.
Есть нормальный IT-бизнес, позволяющий финансировать свои разработки. Про эти разработки и пишем сюда в блог, почитайте наши статьи, вопросы к ним и ответы наших разработчиков — Хабр же технический ресурс, а не коммерческий.
Ну и на yadro.com про свои продукты пишем.
Есть нормальный IT-бизнес, позволяющий финансировать свои разработки. Про эти разработки и пишем сюда в блог, почитайте наши статьи, вопросы к ним и ответы наших разработчиков — Хабр же технический ресурс, а не коммерческий.
Ну и на yadro.com про свои продукты пишем.
UFO just landed and posted this here
AIX требует подложки над аппаратурой в виде PowerVM, проприетарной технологии IBM, которая не доступна в OpenPOWER. Опять же, ввиду закрытости, мы не имеем возможности добавить в AIX поддержку работы на «Bare Metal». Проблема технологическая, решение которой, с политической точки зрения, никому не интересно.
Долгое время главным игроком в сфере безопасного хранения данных оставалась технология RAID.Эту технологию сейчас кто-то смог обогнать по частоте применения? Интересно было бы прочитать кто. Даже если это произошло в какой-то конкретной сфере.
Очень буду ждать сравнения классических технологий RAID и вашей разработки. Хотя не до конца понимаю зачем свою реализацию противопоставлять самой технологии. Не правильнее ли запатентовать свой кастомный уровень.
По «частоте применения», возможно, технология RAID — лидер. По другим критериям, например, «объемы данных», картина, думаю, другая. Все известные мне «облачные» решения не используют RAID для хранения пользовательских данных. А объемы данных там гигантские. Современные классические СХД в связи с ростом объемов данных и увеличением требований к «физической» плотности систем, начинают сталкиваться с теми же ограничениями, что и «облачные системы» (где технологии RAID не находят массового применения). На самом деле, мы не противники RAID и несомненно есть и будут области, где RAID – оптимальный выбор. Мы рассматривали и такой вариант, но пришли к выводу, что использовать в нашем случае RAID — нецелесообразно.
А можно Вас попросить рассказать каким образом при использовании erasure coding гарантируются различные схемы отказоустойчивости, например в документации к одному хранилищу данных написано, что поддерживаются схемы защиты 2d:1n или, например, 3d:1n_1d. То есть поддерживается выход из строя 2 дисков либо 1 ноды, а во втором случае поддерживает выход из строя 3 дисков либо 1 ноды и 1 диска. Вот как такие вещи реализуются? И означает ли это что 100% данные потеряются при выходе из строя, например, 3 дисков при схеме защиты 2d:1n? Но больше всего конечно интересен сам механизм.
Все зависит от архитектуры системы. В нашем случае, все «головы» кластера видят один и тот же набор дисков. Выход из строя «головы» не приводит к потере данных. Только сломавшийся диск требует запуска процедуры восстановления. Когда говорят про схему кодирования N+K (в технологиях erasure coding), подразумевается, что блок с данными разбивается на N фрагментов, по ним считаются дополнительные K, и все это «разлетается» по разным дискам. У нас схема по умолчанию 12+4, соответственно любые 4 диска можно потерять.
В других СХД, архитектура может быть другой. Конкретная «голова» может отвечать за какое-либо число дисков и выход из строя «головы» равнозначен поломке всех дисков, за которые она отвечает. Если, к примеру, «голова» отвечает за 3 диска, а схема 12+4, то можно потерять или 4 диска, или 1 диск и одну «голову» или …
В других СХД, архитектура может быть другой. Конкретная «голова» может отвечать за какое-либо число дисков и выход из строя «головы» равнозначен поломке всех дисков, за которые она отвечает. Если, к примеру, «голова» отвечает за 3 диска, а схема 12+4, то можно потерять или 4 диска, или 1 диск и одну «голову» или …
ААААААА!!!
ААААААААА!!!!11111
Гхм, эээ, простите. :) Просто я в восторге — вот так и надо писать статьи и учебники. Отличный пример хорошей подачи материала. Я очень надеюсь, что такой стиль будет распространяться и вытеснять из практики преподавания нынешний академический стиль.
ААААААААА!!!!11111
Гхм, эээ, простите. :) Просто я в восторге — вот так и надо писать статьи и учебники. Отличный пример хорошей подачи материала. Я очень надеюсь, что такой стиль будет распространяться и вытеснять из практики преподавания нынешний академический стиль.
del
Sign up to leave a comment.
Коды Рида-Соломона. Часть 1 — теория простым языком