РАЗДЕЛ 2. РАЗРАБОТКА СПОСОБА РАСШИРЕНИЯ КЛАССА
ГАРАНТИРОВАННО ОБНАРУЖИВАЕМЫХ ОШИБОК
ПРИ ПЕРЕДАЧЕ ДАННЫХ
В современных условиях, одним из важнейших направлений повышения эффективности обнаружения ошибок передачи данных является расширение класса гарантированно обнаруживаемых ошибок. Важность этого направления повышения эффективности контроля ошибок обусловлена, в первую очередь, ростом объемов передаваемой в компьютерных системах и сетях информации. Указанный фактор, вкупе с ростом требований к надежности передачи данных, снижает эффективность традиционных средств, таких как CRC и CS, обнаруживающих ошибки с некоторой вероятностью и обуславливает необходимость их совершенствования с тем, чтобы обеспечить гарантированное обнаружение основных классов ошибок, возникающих при передаче данных в системах и сетях вычислительной техники.
2.1. Модификация контрольной суммы для гарантированного
обнаружения ошибок ограниченной четной кратности,
Большая часть линий передачи цифровых данных компьютерных систем не использует групповой модуляции передаваемых данных: они передаются побитово в виде последовательности импульсов [18]. В теоретическом плане такие линии соответствуют модели двоичного симметричного канала [20]. Доминирующим типом ошибок для указанного канала являются независимые друг от друга ошибки относительно небольшой кратности, причем распределение вероятностей ошибок различной кратности подчинено биномиальному закону [34]. Поскольку ошибки нечетной кратности гарантированно обнаруживаются как CRC и CS, наиболее важным типом необнаруживаемых ошибок являются ошибки четной малой кратности: от 2 до 6. Этот класс ошибок вероятностно обнаруживается с использованием CS, равно как ошибки кратности 4 и 6 - при применении CRC. Задача состоит в том, чтобы разработать способ модификации контрольной суммы, использование которого позволило бы гарантировать обнаружение 2-6 кратных ошибок. Поскольку расширение класса гарантированно обнаруживаемых ошибок с помощью модифицированной взвешенной контрольной суммы сопряжено с увеличением разрядности контрольного кода, представляется оправданным разработать способ, который бы позволял гибко менять кратность гарантированно обнаруживаемых ошибок. Это позволило бы обеспечивать наперед заданную степень достоверности передачи цифровых данных в компьютерных системах в зависимости от специфики их практического использования.
Выбор, в качестве базового варианта, контрольной суммы обусловлен тем, что этот способ контроля ошибок имеет вычислительную структуру, позволяющую достаточно просто распараллелить вычисления, связанные с контролем ошибок передачи данных.
Для гарантированного обнаружения ошибок четной кратности, не превышающей h, предлагается способ модификации взвешенной контрольной суммы.
Сущность способа состоит в том, что для формирования компонент контрольной суммы предлагается использование опорного множества частично-ортогональных кодов.
Опорным m-компонентным множеством ?m частично-ортогональных кодов порядка h будем называть множество ?m={U1,U2,...,Um}, состоящее из m k-битовых кодов U1,U2,...,Um таких, что сумма по модулю 2 любого их подмножества ?, которое включает в себя не более h таких кодов не равно нулю:
(2.1)
Фактически, это означает, что любое подмножество ? ? ?m, ??? ? h представляет собой ортогональный базис в h-мерном пространстве [28].
Пусть контролируется правильность передачи блока В данных, состоящего из m битов: B={b1,b2,...,bm}, bi?{0,1}, i=1,...,m. Для заданной четной кратности h ошибок, которые должны быть гарантировано обнаружены, всегда возможно сформировать множество ?={U1,U2,...,Um} частично-ортогональных кодов.
Согласно предлагаемому способу модифицированная взвешенная контрольная сумма CS на приемнике и передатчике формируется, как сумма по модулю 2 m (k+1)-разрядных ее компонент W1,W2,...,Wm:
CS=W1?W2?...?Wm. (2.2)
Значение каждой j-той компонента контрольной суммы - Wj, j?{1,...,m} определяется значением одноименного бита bj контролируемого блока и j-тым частично-ортогональным кодом Uj. При этом, компонента Wj формируется как конкатенация j-того бита bj блока В и логического произведения этого бита на каждый из разрядов кода Uj::
. (2.3)
Контрольная сумма, определяемая в соответствии с (2.2) и (2.3) вычисляется отдельно на передатчике и приемнике. Блоки данных на передатчике и приемнике, равно как и составляющие их биты, обозначим как BS ={b1S,b2S,...,bmS} и BR={b1R,b2R,...,bmR} соответственно. После передачи блока данных, контрольная сумма CSS передатчика передается на приемник, где сравнивается с контрольной суммой CSR, вычисленной на приемнике.
Решение о наличии ошибок при передаче блока данных принимается, если отличен от нуля (k+1)-разрядный код ? разницы контрольных сумм передатчика CSS и приемника CSR : , причем компоненты кода ? разности определяются в виде :
(2.4)
Покажем, что предложенная модификация взвешенной контрольной суммы, вычисляемая в соответствии с (2.2) и (2.3), обеспечивает гарантированное обнаружения ошибок нечетной кратности и ошибок, четная кратность которых не превышает заданной порогового значения h.
При возникновении в процессе передачи блока нечетного числа битовых искажений, бит ?1 кода ? разницы контрольных сумм передатчика и приемника в силу (2.4) представляет собой сумму по модулю 2 нечетного количества единичных компонент, которые соответствуют несовпадающим одноименным битам блоков данных на приемнике и передатчике. Соответственно, ?1=1. Это означает, что нечетное число ошибок, возникших в процессе передачи блока данных, гарантированно обнаруживается при использовании предложенного варианта взвешенной контрольной суммы.
При возникновении в пр