Коды Бергера в системах функционального контроля
Классический код с суммированием, или код Бергера, образуется путем приписывания к информационному вектору контрольного вектора, представляющего собой двоичное число <g1 g2 … gk>, равное сумме числа единичных информационных разрядов (равное весу r информационного вектора). Число контрольных разрядов в коде Бергера зависит от числа информационных разрядов и равно (запись
обозначает целое сверху от x). Обозначим классический код с суммированием как S(m,k)-код, где m – длина информационного вектора кода, а k – длина контрольного вектора.
Свойства S(m,k)-кодов по обнаружению ошибок в информационных векторах удобно определять, задавая код в табличной форме, где все информационные векторы распределены на контрольные группы по весу r. Например, в табл. 1 дается S(4,3)-код.
Таблица 1. S(4,3)-код
r | |||||||
Контрольный вектор | |||||||
Коды Бергера имеют довольно большое число необнаруживаемых ошибок в информационных векторах (обозначим данную величину как Nm), что объясняется неравномерностью распределения информационных векторов на контрольные группы. В каждой контрольной группе содержится по информационных векторов. С увеличением значения r до величины
(запись
обозначает целое снизу от x) число информационных векторов в контрольной группе возрастает, а с дальнейшим приближением к величине m аналогичным образом уменьшается. Минимальным количеством необнаруживаемых ошибок обладает такой (m,k)-код, у которого все
информационных векторов равномерно распределены по
контрольным группам [15, 16]. Этот код является оптимальным (m,k)-кодом по критерию минимума числа необнаруживаемых искажений в информационных векторах. Число необнаруживаемых ошибок в нем равно
(1)
Оптимальный (4,3)-код имеет всего 16 необнаруживаемых ошибок в информационных векторах, что более чем в три раза меньше, чем у S(4,3)-кода.
«Близость» кода с суммированием к оптимальному (m,k)-коду определяется коэффициентом эффективности ξ:
(2)
Чем ближе значение ξ к 1, тем эффективнее код с позиции обнаружения искажений в информационных векторах при заданных значениях длин информационных и контрольных векторов. S(4,3)-код, например, имеет значение ξ=0,2963. У других кодов Бергера значение ξ, как правило, не превышает величины 0,5. Таким образом, коды Бергера далеки от оптимальных (m,k)-кодов.