Здравствуйте, друзья! В прошлый раз мы с вами начали говорить о том, как коды Рида-Соломона помогают обеспечивать необходимый уровень надежности хранения данных. Сегодня остановимся немного подробнее на арифметике полей Галуа, которая используется в расчётах.
Читать полностью »
Рубрика «поля галуа»
Коды Рида-Соломона. Часть 2 — арифметика полей Галуа
2017-11-02 в 3:32, admin, рубрики: Erasure Coding, Алгоритмы, Блог компании YADRO, восстановление информации, коды Рида-Соломона, поля галуаКоды Рида-Соломона. Часть 1 — теория простым языком
2017-08-24 в 4:33, admin, рубрики: Erasure Coding, Алгоритмы, Блог компании YADRO, восстановление информации, коды Рида-Соломона, поля галуаДобрый день! Меня зовут Максим, в YADRO, кроме всего прочего, я занимаюсь разработкой подсистемы, отвечающей за надежное хранение данных. Готовлю небольшой цикл статей про коды Рида-Соломона — теоретическую основу, практическую реализацию, применяемые на практике программные и аппаратные оптимизации. На Хабре и в остальной сети есть хорошие статьи по вопросам этой области — но по ним сложно разобраться, если ты новичок в теме. В этой статье я попытаюсь дать понятное введение в коды Рида-Соломона, а в следующих выпусках напишу, как все это запрограммировать.
Корректирующие коды «на пальцах»
2017-05-09 в 21:15, admin, рубрики: алгебра, Алгоритмы, кодирование, корректирующие коды, линейные коды, математика, математика на пальцах, поля галуа, метки: корректирующие коды, линейные коды
Корректирующие коды — это коды, которые могут обнаружить и (если повезёт) исправить ошибки, возникшие при передаче данных. Даже если вы ничего не слышали о них, то наверняка встречали аббревиатуру CRC в списке файлов в ZIP-архиве или даже надпись ECC на планке памяти. А кто-то, может быть, задумывался, как так получается, что если поцарапать DVD-диск, то данные всё равно считываются без ошибок (конечно, если царапина не в сантиметр толщиной и не разрезала диск пополам).
Как нетрудно догадаться, ко всему этому причастны корректирующие коды. Собственно, ECC так и расшифровывается — «error-correcting code», то есть «код, исправляющий ошибки». А CRC — это один из алгоритмов, обнаруживающих ошибки в данных. Исправить он их не может, но часто это и не требуется.
Давайте же разберёмся, что это такое.
Для понимания статьи не нужны никакие специальные знания. Достаточно лишь понимать, что такое вектор и матрица, как они перемножаются и как с их помощью записать систему линейных уравнений.
Внимание! Много текста и мало картинок. Я постарался всё объяснить, но без карандаша и бумаги текст может показаться немного запутанным.
Начнем с математики. Векторизация вычислений в реализации технологии RAID-6
2017-04-19 в 9:15, admin, рубрики: raid, raid6, Алгоритмы, Блог компании RAIDIX, высокая производительность, конечные поля, контрольная сумма, математика, поля галуа, системное программирование, системы хранения данных, СХД, хранение данныхМногие помнят публикацию о «Рэйдикс» на Хабре «Как разработчики сидели в Петербурге и тихо ели грибы», в которой партнеры кратко изложили историю появления нашего продукта. Поэтому в первой статье своего Хаброблога мы бы хотели погрузиться в математические основы технологий RAIDIX.
Конечное поле GF(256) и немного магии
2016-03-14 в 8:52, admin, рубрики: aes, c++, битовая алхимия, ненормальное программирование, поля галуа, шаблоны c++, метки: поля галуаВведение
Будучи студентом я посещаю занятия по криптографии. И разумеется этот курс не мог обойти вниманием стандарт AES.
При реализации данного алгоритма встает вопрос о реализации полей GF(2^8), что будет освещено в данной статье. Будут рассмотрены: битовая магия для умножения элементов поля, шаблоны для генерации таблиц замен на этапе компиляции.
Вторая часть предполагает, что читатель имеет доступ к компилятору с поддержкой C++14. Первая часть будет написана в стиле Си.
Читать полностью »