ОПРЕДЕЛЕНИЕ ЧИСЛА НЕОБНАРУЖИВАЕМЫХ ОШИБОК ЦИКЛИЧЕСКИМИ КОДАМИ

АННОТАЦИЯ

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

ABSTRACT

The paper studies the patterns of construction and error detection characteristics of cyclic codes. The principles and previously unknown patterns of construction of the studied codes are given. The dependence of the number of control groups of cyclic codes on the number of members of the generating polynomials and their degree is proved. A formula for calculating the number of undetectable errors by any cyclic codes is obtained. A theorem is proved that only when using a polynomial with a free term, the maximum number of errors in cyclic codes is found. The concept of an optimal code with a parity check by the criterion of complete detection of errors of even multiplicity and a certain proportion of errors of odd multiplicity is introduced. A theorem is proved on the existence among the classes of cyclic codes, parity-checking codes with better indicators of detecting characteristics compared to classical parity-checking codes. Recommendations are given on the choice of generating polynomials for constructing cyclic codes with the theoretically maximum possible number of error detection.

Ключевые слова: теория кодирования; циклические коды; число необнаруживаемых ошибок; расчет ошибок; оптимальные циклические коды.

Keywords: coding theory; cyclic codes; number of undetectable errors; error calculation; optimal cyclic codes.

Введение. Начиная с 50-х гг. XX столетия бурное развитие получило направление теории кодирования информации, в силу необходимости защиты от помех и шифрования передаваемой информации по каналам связи. Именно к этому периоду относятся впервые предложенные и разработки различных помехоустойчивых кодов, к примеру, таких как коды Хэмминга, Бергера, циклических кодов (Cyclic Redundancy Code - CRC) и др. [1 – 4]. Способы построения перечисленных кодов различны, и в связи с этим, они обладают разными характеристиками по обнаружению ошибок. Ошибки же в информационном m-векторе имеют различную кратность – d, , и вид – однонаправленные и разнонаправленные [5, 6].

Методы защиты данных на основе кодирования, при этом учитывающие особенности возникновения ошибок в канале связи, на выходах диагностируемых устройств при их функциональном диагностировании при помощи схем контроля, позволяют строить системы с высокими обнаруживающими характеристиками [7 – 10]. В этом случае учитываются свойства обнаружения того или иного вида ошибок или их кратности конкретным помехоустойчивым кодом и характер проявляемых ошибок в канале связи, в диагностируемых устройствах. Для этой цели заранее необходим подсчет числа необнаруживаемых ошибок применяемого кода в основе системы. Это делается для заблаговременного определения уровня надежности системы, канала связи и в некоторых случаях для принятия соответствующих мер по ее повышению. К примеру, в дискретных устройствах с самопроверяемыми схемами используют проектирование системы функционального контроля специальными методами, таких как, контроль рабочих выходов диагностируемого устройства на основе выделения контролепригодных групп, проектирование диагностируемых устройств с определенной зависимостью выходов на проявление только конкретного вида ошибок, использование логического дополнения при синтезе систем функционального контроля и т.д. [11 – 15].

Работа посвящена изложению установленных в ходе исследований закономерностей построения циклических кодов. Полученные результаты также могут быть полезны и при решении задач обработки и передачи данных.

1. Принцип построения полиномиальных кодов

Циклические коды (CRC), или их еще называют полиномиальными, относят к классу линейных систематических кодов [2, 16, 17]. Такие коды обозначают как (m,k)-коды, где m – длина информационного вектора; k – длина контрольного вектора. При построении полиномиальных кодов подразумеваются представление вектора информационных данных в виде полинома M(x) степени deg M=m–1. К примеру, вектор вида 101101 можно представить, как:

После исключения нулевых слагаемых, получаем полином вида:

                                          (1)

Название циклических (Cyclic) такие коды получили благодаря тому, что если полином (1) умножить на одночлен вида x^j, где deg j> степени полинома (1), то полученный полином будет представлять тот же самый полином (1), но смещенный на степень j. Характеристики по обнаружению ошибок полученного полинома будут одинаковыми с характеристиками полинома (1) [2, 17].

При построении циклических кодов для получения систематического кода используют метод деления с остатком [2]. Алгоритм получения кодового полинома V(x) методом деления с остатком следующий:

1. Подбирают образующий полином P(x) для образования кода с заданными характеристиками, при этом, k=deg P<deg M;
2. Полином M(x) умножают на значение x^degP для смещения информационных разрядов на k позиций в старшие разряды;
3. Полином x^degPM(x) делят на полином P(x);
4. Остаток от деления R(x) прибавляют к x^degPM(x).

Таким образом формируется кодовый вектор:

                               (2)

Для обнаружения ошибок производят деление вектора V(x) на выбранный полином P(x), тогда, если R(x)=0, считают, что искажение не произошло, если R(x)≠0 – имеется искажение. Например, если вектор 101101 преобразуем в кодовый вектор V(x) с помощью образующего полинома x³+x+1, то получим вектор вида 101101011 или V(x)=x⁸+x⁶+x⁵+x³+x+1. При операции деления получаем:т.е. R(x)=0.

Специально введем ошибку в сформированный кодовый вектор – 101001011. Осуществим деление искаженного вектора на образующий полином:

т.е. R(x)=x²+x+1≠0.

Таким образом вычисляется синдром ошибки в циклических кодах.

2. Закономерности построения циклических кодов с различными характеристиками

Свойства кодов по обнаружению ошибок зависят от особенностей распределения информационных m-векторов по контрольным k-векторам. В работе [18] было доказано, что только при использовании максимально возможного числа контрольных векторов и при равномерном распределении информационных векторов по контрольным можно добиться максимального обнаружения ошибок в кодах. Исследования большинства кодов показывают, что не все помехозащищенные коды строятся с соблюдением вышеприведенной зависимостью, следовательно, обладают «не лучшими» характеристиками.

Анализ зависимости распределения информационных векторов по контрольным группам, а также некоторые свойства обнаружения ошибок разделимых кодов удобно рассматривать в табличной форме их задания. К примеру, в табл. 1 и табл. 2 приведено распределение m векторов по контрольным группам кодов, образованные с помощью полиномов x³+x и x³+x+1.

Таблица 1.

Распределение информационных векторов при полиноме x³+x

Таблица 2.

Распределение информационных векторов при полиноме x³+x+1

Из таблиц следует, что при разных полиномах P(x) информационные векторы распределяются по контрольным группам по разному, т.е. могут использоваться не все контрольные группы. При полиноме x³+x+1 информационные векторы распределены по всем контрольным группам, а при полиноме x³+x, информационные векторы распределены только по контрольным векторам: <000>, <010>, <100> и <110>.

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

При использовании полинома x³+x рабочими контрольными группами являются группы вышеуказанных контрольных векторов. При использовании полинома x³+x+1 – все группы векторов из множества 2^k.

В ходе исследований [15, 17, 19, 20] на основе вышеприведенного анализа распределения информационных векторов по контрольным группам циклических кодов установлена зависимость числа рабочих контрольных групп  кода при разных полиномах P(x):

                                             (3)

где l – степень наименьшего члена P(x).

На основе (3) для полинома x³+x получаем , для x³+x+1 –  рабочих контрольных групп (см. табл. 1, 2).

3. Методология исследования. Определение числа необнаруживаемых ошибок циклическими кодами

Количество используемых рабочих контрольных групп в полиномиальных кодах определяет число необнаруживаемых ошибок такими кодами. В [18] доказано, что коды имеют наименьшее число необнаруживаемых ошибок при заданных значениях m и k только при равномерном распределении информационных векторов по всем контрольным группам, а при циклических кодах не при всех образующих полиномах это имеет место.

Определение 2. Оптимальными по критерию минимума числа необнаруживаемых ошибок называются такие коды, которые при заданных значениях m и k имеют наименьшее число необнаруживаемых ошибок в информационных векторах кодовых слов.

Число необнаруживаемых ошибок в таких кодах определяется формулой [21]:

                                 (4)

Общее же число искажений в m информационном векторе выражается [21]:

                                     (5)

В ходе исследований на основе выражения (3) и формулы (4) получена формула для определения числа необнаруживаемых ошибок циклическими кодами при разных полиномах P(x):

                                (6)

Теорема 1. Код, построенный с помощью полинома вида x^j, , не является помехоустойчивым кодом.

Доказательство. Количество искажений в кодах не обнаруживающих ошибки определяется формулой (5). Используя формулу (6) определим число необнаруживаемых ошибок кодом, построенным с помощью полинома вида x^j и т.к. для полиномиальных кодов k=deg P и в данном случае deg P=j=l, имеем:

Получаем, что , а значит, такой код не обнаруживает ни одной ошибки.

Теорема 1 доказана.

Теорема 2. Код, построенный с помощью полинома P(x) со значением l=0, deg P>0, является оптимальным кодом.

Доказательство. Определим число необнаруживаемых ошибок полиномиальными кодами, построенных с помощью полиномов P(x) со значением l=0, deg P>0. Тогда, на основе (6) и учитывая, что l=0, получаем:

Отсюда следует, что .

Теорема 2 доказана.

Заметим, что выше рассмотренный полином x³+x+1 порождает оптимальный полиномиальный код.

Ошибки в кодовом слове имеют разную кратность. Кратностью ошибки d, где , называется количество искажаемых разрядов информационного вектора в кодовом слове. Искажения d=1, так называемые одиночные ошибки, обнаруживают все помехоустойчивые коды. При многократных ошибках, когда d>1, начинают проявляться ошибки разных видов: монотонные, симметричные и асимметричные [6]. Существуют коды полностью обнаруживающие ошибки определенных видов и кратностей.

Определение 3. Назовем оптимальным кодом с проверкой на четность по критерию обнаружения всех ошибок нечетных кратностей и минимума числа необнаруживаемых ошибок такой систематический код, который обнаруживает все ошибки нечетной кратности и некоторую долю ошибок четной кратности, в сумме имеющий минимальное число необнаруживаемых ошибок при заданных значениях m и k.

В ходе исследований циклических кодов в их классах были обнаружены такие коды.

Теорема 3. Любой полином Р(х), со значением l=0, j>l, deg P>1 и c четным количеством членов, порождает оптимальный код с проверкой на четность.

Доказательство. Предположим, что

Если в разложение P(x) входит полином x+1, то справедливо разложение P(x)=(x+1)P"(x) для некоторого P"(x), и тогда имеем:

Воспользуемся теоремой Безу, и подставляя вместо х единицу, получаем:

Так как . Тогда, если число членов V(x) четно, то , если нечетно –  Значит, код порожденный полиномом с четным количеством членов является кодом проверкой на четность.

С другой стороны, на основе (6) число необнаруживаемых ошибок при  равно , а значит, код с проверкой на четность при l≠0 не обнаруживает большее количество ошибок, чем при l=0. Также в теореме 2 доказано, что при l=0, формируются коды с минимальным числом необнаруживаемых ошибок.

Теорема 3 доказана.

Обсуждение результатов исследования

Вышеприведенные теоремы о циклических кодах очень полезны при выборе образующих полиномов для построения эффективных кодов по обнаружению ошибок. Полученная формула (6) позволяет заранее определять число возможных необнаруживаемых ошибок в кодовом слове.

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

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

Положения, установленные в работе, могут быть полезны при проектировании систем обработки и передачи информации, а также систем функционального диагностирования дискретных устройств на основе кодовых методов.

Список литературы:

1. Ryan W.E., Lin S. Channel codes: Classical and Modern. – Cambridge University Press, 2009, 708 р.
2. Peterson W. W., Error correcting codes, МТ Press, Саmbridge, L'аss. 1961.
3. Hamming, R.W. Error detecting and correcting Codes / R.W. Hamming // Bell System Technical Journal, 1950. – 29 (2). – pp. 147-160. – MR0035935.
4. Berger, J. M. A Note on error detection codes for asymmetric channels / J. M. Berger // Information and Control. – 1961. – Vol. 4, Issue 1. – Pp. 68-73. – DOI: 10.1016/S0019-9958(61)80037-5.
5. Щербаков Н. С. Самокорректирующиеся дискретные устройства. – М.: Машиностроение, 1975. – 216 с.
6. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Классификация ошибок в информационных векторах систематических кодов // Известия вузов. Приборостроение. – 2015. – Том 58. – №5. – С. 333-343. – DOI: 10.17586/0021-3454-2015-58-5-333-343.
7. Bennetts, R.G. Design of testable logic circuits. London; Reading Mass.:Addison-Wesley Pub. Co. 1984, 164 p.
8. Morosow A., Sapozhnikov V.V., Sapozhnikov Vl.V., Goessel M. Self-Checking combinational circuits with unidirectionally independent outputs // VLSI Design. – 1998. – Vol. 5. – Issue 4. – Pp. 333-345. – DOI: 10.1155/1998/20389.
9. Sogomonyan E.S., Gössel M. Design of self-testing and on-line fault detection combinational circuits with weakly independent outputs // Journal of Electronic Testing: Theory and Applications. – 1993. – Vol. 4. – Issue 4. – Pp. 267-281. – DOI:10.1007/BF00971975.
10. Qiu W., Zhang X., Li H., Wang Z., Zhang Y., Zheng Z. Concurrent all-cell error detection in semi-systolic multiplier using linear codes // Applied Mathematics & Information Sciences. – 2013. – Vol. 7. – No 3. – Рp. 947–954.
11. Z. Navabi “Digital system test and testable design: using HDL models and architectures”, Springer Science+Business Media, LLC 2011, 435 p.
12. F.Y. Busaba, and P.K. Lala “Self-checking combinational circuit design for single and unidirectional multibit errors”, Journal of Electronic Testing: Theory and Applications, 1994, Vol. 5, Issue 1, pp. 19-28, doi: 10.1007/BF00971960.
13. Абдуллаев Р.Б. Синтез полностью самопроверяемых схем встроенного контроля на основе полиномиальных кодов для комбинационных логических устройств // Автоматика на транспорте. – 2021. – Том 7. – №3. – С. 452-476. – DOI: 10.20295/2412-9186-2021-7-3-452-476.
14. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В. Коды с суммированием для систем технического диагностирования. Том 1: Классические коды Бергера и их модификации. – М.: Наука, 2020. – 383 с.
15. Сапожников В.В., Сапожников Вл.В., Ефанов Д.В., Абдуллаев Р.Б. Особенности организации систем функционального контроля комбинационных схем на основе полиномиальных кодов // Известия Петербургского университета путей сообщения. – 2018. – Т.15. – №3. – С. 432-445.
16. Sellers F. F., Hsiao M.-Y., Bearnson L.W. Error detecting logic for digital computers. – New York: McGraw-Hill, 1968, XXI + 295 p.
17. Efanov D., Plotnikov D., Sapozhnikov V., Sapozhnikov Vl., Abdullaev R. Experimental studies of polynomial codes in concurrent error detection systems of combinational logical circuits // Proceedings of 16th IEEE East-West Design & Test Symposium (EWDTS’2018), Kazan, Russia, September 14-17, 2018, pp. 184-190, doi: 10.1109/EWDTS.2018.8524684.
18. Сапожников, В. В. Коды Хэмминга в системах функционального контроля логических устройств: монография / В. В. Сапожников, Вл. В. Сапожников, Д. В. Ефанов. – СПб.: Наука, 2018. – 151 с.
19. Abdullaev R.B., Efanov D.V., Sapozhnikov V.V., Sapozhnikov Vl.V. Polynomial code with detecting the symmetric  and asymmetric errors in the data vectors // Proceedings of 17th IEEE East-West Design & Test Symposium (EWDTS’2019), Batumi, Georgia, September 13-16, 2019, pp. 157-161, doi: 10.1109/EWDTS.2019.8884451.
20. Abdullaev R., Efanov D. Polynomial codes properties application in concurrent error-detection systems of combinational logic devices // Proceedings of 19th IEEE East-West Design & Test Symposium (EWDTS’2021), Batumi, Georgia, September 10-13, 2021, pp. 40-46. – DOI:10.1109/EWDTS52692.2021.9580992.
21. Sapozhnikov V., Sapozhnikov Vl., Efanov D., Blyudov A. Analysis of error-detection possibilities of CED circuits based on Hamming and Berger Codes // Proceedings of 11th IEEE East-West Design & Test Symposium (EWDTS’2013), Rostov-on-Don, Russia, September 27-30, 2013, pp. 200-207, doi: 10.1109/EWDTS.2013.6673097.