РАЗДЕЛ 2. РАЗРАБОТКА МЕТОДОВ ПОВЫШЕНИЯ
НАДЕЖНОСТИ ОБНАРУЖЕНИЯ ОШИБОК ПЕРЕДАЧИ
ДАННЫХ С ИСПОЛЬЗОВАНИЕМ КОНТРОЛЬНЫХ СУММ
Контрольная сумма является простым средством контроля ошибок передачи блока
символов, допускающим распараллеливание при реализации контроля на аппаратном
уровне. Основным недостатком контрольной суммы, снижающим эффективность ее
использования для контроля ошибок, является меньшая надежность по сравнению с
CRC. С другой стороны, важным достоинством контрольной суммы является
возможность ее адаптация к преобладающему в канале типу ошибок путем
специального кодирования ее компонент. Использование CRC не предоставляет такой
возможности.
Большинство проводных линий передачи цифровых данных в компьютерных системах и
сетях в плане возникновения в них ошибок соответствуют теоретической модели
двоичного симметричного канала. Исходя из этого, важным направлением в
повышении эффективности использования контрольных сумм, как средства
обнаружения ошибок передачи данных в вычислительных системах и сетях является
разработка средств кодирования компонент контрольной суммы применительно к
ошибкам, преобладающим в двоичном симметричном канале.
2.1. Анализ возможностей повышения надежности контрольной
суммы при обнаружении ошибок в двоичном симметричном
канале.
Использование контрольной суммы, как способа обнаружения ошибок передачи блока
цифровых данных обеспечивает наибольшую эффективность реализации функций
контроля, как на аппаратном, так и на программном уровне. Основным достоинством
контрольной суммы по сравнению с CRC в современных условиях резкого роста
скоростей передачи данных является принципиальная возможность распараллелить
вычисление компонент контрольной суммы. Основной недостаток использования
контрольной суммы состоит в том, что надежность обнаружения ошибок четной
кратности существенно меньше по сравнению с CRC. Для линий передачи данных,
соответствующих модели двоичного симметричного канала, в которых вероятность
возникновения ошибки быстро уменьшается при увеличении ее кратности, наиболее
критичным для использования контрольной суммы является низкая вероятность
обнаружения двукратной ошибки, которая гарантированно обнаруживается при
применении CRC. Исходя из этого, важной задачей на пути создания
высокопроизводительных средств контроля ошибок передачи данных является поиск
возможностей повышения надежности контрольной суммы при обнаружении двукратных
ошибок.
Контролируемый блок В состоит из m бит: B={b1,b2,…,bm}, blО{0,1},l=1,…,m и
разделяется на t=m/n n-разрядные группы бит. Каждая j–тая группа из n смежных
бит образует контрольный символ , j=1,2,…,t,"iО{1,…,n}: xiО{0,1}.
Соответственно, блок В может быть представлен в виде последовательности t = m/n
символов: B={X1,X2,…,Xt}, XjО{0,1,…,2n-1}.
Контрольная сумма CS разрядностью r формируется в виде суммы по модулю два t =
m/n r-разрядных контрольных кодов V1,V2,…,Vt : CS=V1ЕV2Е…ЕVt. Каждый j-тый из
этих кодов–, jО{1,2,…,t} зависит от j-го символа контролируемого блока:
Vj=F(Xj), где F={f1,f2,…,fr}– система из r булевых функций f1,f2,…,fr,
определенных на n двоичных переменных. Если обозначить через CSS контрольную
сумму, вычисляемую на передатчике CSs=Vs1ЕVs2 Е…ЕVst , а через CSr –
контрольную сумму, вычисляемую на приемнике: CSr=Vr1 ЕVr2 Е…ЕVrt , то ошибка
детектируется по ненулевому значению r-разрядного кода разности контрольных
сумм на приемнике и передатчике . В результате ошибок передачи символов по
линии связи они искажаются, то есть при возникновении ошибки передачи j–того
символа Xj, их коды на приемнике и передатчике не одинаковы: Xsj № Xrj.
Ошибка не обнаруживается в двух случаях:
Во-первых, если для двух разных символов Х и Y (X№Y), их контрольные коды
совпадают: F(X)=F(Y).
Во-вторых, если с ошибками будут переданы k символов блока, номера которых
образуют множество Q такое, что .
При использовании традиционной контрольной суммы предполагается, что передача
блока производится по байтам (в этом случае n=8) или по словам (n=16).
Соответственно, в первом случае, символом является байт, а во втором – слово.
Длина r контрольных кодов равна длине n символа: r=n, а сами контрольные коды
совпадают с одноименными символами: "lО{1,…,t}: Vl=Xl. Соответственно,
контрольная сумма вычисляется как поразрядная сумма по модулю 2 символов блока
CS=V1ЕV2Е…ЕVt = X1 Е X2 Е…ЕXt. При этом булевы функции, составляющие
преобразование F имеют вид: f1(X)=x1, f2(X)=x2,…,fr(X)=xr. В силу однозначности
преобразования F, контрольные коды двух разных символов всегда различны и
ошибки любой кратности, меньшей или равной n, вызвавшие искажения разрядов
одного символа всегда будут обнаруживаться традиционной контрольной суммой.
Однако, при возникновении ошибок передачи k символов блока, номера которых
образуют множество Q, ошибки не будут обнаружены, если . В частности,
двукратная ошибка не обнаруживается с использованием традиционной контрольной
суммы, если ошибки вызвали искажение одноименного разряда двух разных
символов.
Для бинарного симметричного канала вероятность того, что двукратная ошибка не
будет обнаружена с использованием традиционной контрольной суммы определяется
исходя из следующих соображений: общее число вариантов локализации двух ошибок
в блоке составляет mЧ(m-1)/2, в то время как количество вариантов локализации
пары ошибок в одноименных разрядах символов - mЧ(m/n-1)/2. Следовательно,
вероятность Р20 того, что двукратная ошибка не будет обнаружена традиционной
контрольной суммой определяется как отн
- Київ+380960830922