ivdon3@bk.ru
Работа посвящена поиску эффективного метода декодирования для нового класса бинарных кодов, корректирующих стирания. Рассматриваемые коды задаются кодирующей матрицей, имеющей ограничения на веса столбцов (МРСт-коды). Для работы с построенными кодами используются декодер по информационным совокупностям и декодер по принципу распространения доверия, адаптированные для случая работы со стираниями. В работе проведены эксперименты по определению скорости декодирования и корректирующей способности этих методов применительно к названным классам помехоустойчивых кодов. В случае МРСт-кодов декодер по принципу распространения доверия значительно выигрывает по скорости по сравнению с декодером по информационным совокупностям, однако незначительно проигрывает по уровню корректирующей способности.
Ключевые слова: каналы со стираниями, распределенные отказоустойчивые системы хранения данных, код с равновесными столбцами, декодер по информационным совокупностям, декодер по принципу распространения доверия, РСт-код, МРСт-код
Во всех каналах передачи данных возникают непреднамеренных ошибки. Стандартным способом борьбы с ними является использование помехоустойчивых кодеков, основанных на применении алгебраических кодов исправления ошибок. Существуют каналы передачи, в которых возникает особый вид ошибок – стирания, т.е. разновидность ошибки, при которой известно местоположение ошибки, но не известна ее величина. В теории кодирования утверждается, что методы борьбы с ошибками могут быть применены для защиты данных от стираний, однако, эти утверждения не сопровождаются подробностями. Данная работа восполняет этот пробел. Построены алгоритмы исправления стираний с помощью произвольных декодеров для кодов, корректирующих ошибки. Сформулированы леммы о корректности построенных алгоритмов, получены некоторые оценки вероятности успешного декодирования.
Ключевые слова: каналы со стираниями, помехоустойчивый код, алгебраический код, декодер кода исправления ошибок, алгоритм исправления стираний