Исследование разделяющей избыточности расширенных кодов Хэмминга

L-разделяющей избыточностью называется минимальное число строк в L-разделяющей проверочной матрице линейного кода. Точное значение L-разделяющей избыточности для произвольного линейного кода неизвестно. В данной работе мы исследуем данное понятие для расширенного кода Хэмминга, широко применяющегося во многих современных системах памяти, таких как RAID 2 и ECC, и предлагаем новый подход для получения нижней границы для данной величины. Также мы исследуем связь данного понятия с понятием блокирующих множеств в аффинном пространстве.

Цель работы заключается в выводе минимальной L-разделяющей избыточности расширенных кодов Хэмминга и построении явных конструкций проверочных матриц, обладающих данным свойством. Задачи, поставленные в рамках данной работы, заключаются в следующем: анализ существующих конструкций L-разделяющих матриц линейных кодов, переформулировка задачи поиска L-разделяющей избыточности расширенных кодов Хэмминга на язык булевых функций, получение проверочных матриц, обладающих L-разделяющей избыточностью и исследование связи данной задачи с понятием блокирующих множеств в аффинном пространстве.

Линейные коды широко применяются в современных телекоммуникационных системах для исправления ошибок и стираний, возникающих в канале с шумом. Для произвольного линейного кода не ясно как построить алгоритм одновременного исправления ошибок и стираний даже если для данного кода известны эффективные алгоритмы исправления ошибок и стираний по отдельности. Было предложено добавлять строки в проверочную матрицу линейного кода таким образом, чтобы удаление из расширенной проверочной матрицы столбцов, определяемых локализацией стираний, приводило бы к проверочной матрице укороченного кода с тем же рангом, что и исходная матрица. Матрица, позволяющая провести данную процедуру для L-стираний, называется L-разделяющей. 

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

Мы хотим построить для кода C L-разделяющую матрицу с минимально возможным числом строк, обозначаемым через \(r_{L}(C)\) . В случае произвольного линейного кода C для данной величины известны лишь довольно грубые оценки. Поэтому в данной работе величина \(r_{L}(C)\) исследуется для расширенных кодов Хэмминга, алгебраическая структура которых позволяет переформулировать задачу нахождения нижней границы \(r_{L}(C)\) на языке булевых функций. Множество аффинных булевых функций от m переменных называется t-аннулирующим, если для любого множества из не более чем t точек найдется  функция из множества, обращающаяся на них в ноль. Обозначим через \(R_{t}(m)\) минимально возможную мощность такого множества. В работе доказано, что \(r_{L}(C) \geq R_{L}(m)\), где код C это расширенный код Хэмминга длины \(2^m\). Для нахождения величины \(R_{t}(m)\) был применен алгебраическо-комбинаторный подход.

 

В данной работе рассмотрена проблема построения вычислительно-эффективного способа исправления ошибок и стираний произвольным линейным кодом путем построения L-разделяющих проверочных матриц с минимально-возможным числом строк. Также приведен краткий литературный обзор, описывающий основные этапы и пути развития в построении и выводе границ на размер L-разделяющих проверочных матриц различных классов линейных кодов. В данной работе эта задача рассмотрена применительно к расширенным кодам Хэмминга, предложен новый подход для нахождения их L-разделяющей избыточности, связанный с переформулировкой исходной задачи на языке булевых функций. Применение данного подхода позволило получить новые нижние оценки для данной величины при небольших значениях L. Также исследована связь понятия m-аннулирующего множества булевых функций и блокирующих множеств в афинном пространстве, которая, скорее всего, позволит получить более точные границы L-разделяющих избыточностей расширенных кодов Хэмминга.

 

 

-)K. A. S. Abdel-Ghaffar and J. H. Weber, Separating erasures from errors for decoding, in Proc. IEEE Int. Symp. on Inf. Theory (ISIT), Toronto, Canada, pp. 215-219, July 6-11, 2008.
-)K. A. S. Abdel-Ghaffar and J. H. Weber, Parity-check matrices separating erasures from errors, IEEE Trans. Inf. Theory, vol.59, no.6, pp. 3332-3346, Jun. 2013.
-)G. Van de Voorde, Constructing Minimal Blocking Sets Using Field Reduction, Journal of Combinatorial Designs, vol. 24, issue 1, pp. 3652, January 2016.
-)A. A. Bruen and B. L. Rothschild, “Lower bounds on blocking sets”, Pacific Journals of Mathematics, vol. 118, No. 2, pp. 303-311, 1985.
-)K. A. S. Abdel-Ghaffar and J. H. Weber, “Parity-check matrices separating
erasures from errors,” IEEE Trans. Inf. Theory, vol.59, no.6, pp.
3332-3346, Jun. 2013.

Separating redundancy is the minimum number of rows of an L-separating parity check matrix of an arbitrary block codes. The exact value of separating redundancy is unknown in general case. In this paper we investigate separating redundancy of extended Hamming codes and develop a new approach for evaluating its’ lower bound. We obtain new lower bounds for small values of L. Also we investigate the relationship between separating redundancy and the size of blocking sets in affine spaces.