Выполните контроль циклическим избыточным кодом

В этом примере показано, как выполнить контроль циклическим избыточным кодом (CRC) на битах номера. CRCs используются, чтобы обнаружить ошибки в передаче данных в цифровых системах. Когда часть данных отправляется, короткое контрольное число присоединено к нему. Контрольное число получено полиномиальным делением с битами в данных. Когда данные получены, полиномиальное деление повторяется, и результат по сравнению с контрольным числом. Если результаты отличаются, то данные были повреждены во время передачи.

Вычислите контрольное число вручную

Запустите с 16-битного двоичного числа, которое является сообщением, которое будет передано:

1101100111011010

Чтобы получить контрольное число, разделите этот номер на полином x3+x2+x+1. Можно представлять этот полином с его коэффициентами: 1111.

Деление выполняется на шагах, и после каждого шага, полиномиальный делитель выравнивается с крайним левым 1 в номере. Поскольку результат деления на четыре полинома термина имеет три бита (в общем делении на полином длины n+1 производит контрольное число длины n), добавьте номер с 000 вычислить остаток. На каждом шаге результат использует побитовое исключающее ИЛИ управляющихся четырех битов, и все другие биты неизменны.

Первый дивизион

1101100111011010 000
1111
----------------
0010100111011010 000

Каждое последовательное деление работает с результатом предыдущего шага, таким образом, второе деление

0010100111011010 000
  1111
----------------
0001010111011010 000

Деление завершается, если дивиденд является всеми нулями. Полное деление, включая вышеупомянутые два шага,

1101100111011010 000
1111
0010100111011010 000
  1111
0001010111011010 000
   1111
0000101111011010 000
    1111
0000010011011010 000
     1111
0000001101011010 000
      1111
0000000010011010 000
        1111
0000000001101010 000
         1111
0000000000010010 000
           1111
0000000000001100 000
            1111
0000000000000011 000
              11 11
0000000000000000 110

Биты остатка, 110, контрольное число для этого сообщения.

Вычислите контрольное число программно

В MATLAB® можно выполнить эту ту же операцию, чтобы получить контрольное число с помощью битовых операций. Во-первых, задайте переменные для сообщения и полиномиального делителя. Используйте 32-битные целые числа без знака так, чтобы дополнительные биты были доступны для остатка.

message = 0b1101100111011010u32;
messageLength = 16;
divisor = 0b1111u32;
divisorDegree = 3;

Затем инициализируйте полиномиальный делитель. Используйте dec2bin отобразить биты результата.

divisor = bitshift(divisor,messageLength-divisorDegree-1);
dec2bin(divisor)
ans = 
'1111000000000000'

Теперь переключите делитель и сообщение так, чтобы у них было правильное количество битов (16 битов для сообщения и 3 бита для остатка).

divisor = bitshift(divisor,divisorDegree);
remainder = bitshift(message,divisorDegree);
dec2bin(divisor)
ans = 
'1111000000000000000'
dec2bin(remainder)
ans = 
'1101100111011010000'

Выполните шаги деления CRC с помощью for цикл. for цикл всегда совершенствует один бит каждый шаг, поэтому включайте проверку, чтобы видеть, является ли текущая цифра 1. Если текущая цифра является 1, то шаг деления выполняется; в противном случае цикл совершенствуется немного и продолжается.

for k = 1:messageLength
    if bitget(remainder,messageLength+divisorDegree)
        remainder = bitxor(remainder,divisor);
    end
    remainder = bitshift(remainder,1);
end

Переключите биты остатка к праву получить контрольное число для операции.

CRC_check_value = bitshift(remainder,-messageLength);
dec2bin(CRC_check_value)
ans = 
'110'

Проверяйте целостность сообщения

Можно использовать контрольное число, чтобы проверить целостность сообщения путем повторения той же операции деления. Однако вместо того, чтобы использовать остаток от 000 чтобы запуститься, используйте контрольное число 110. Если сообщение будет безошибочно, то результатом деления будет нуль.

Сбросьте переменную остатка и добавьте контрольное число CRC в биты остатка с помощью побитового ИЛИ. Введите ошибку в сообщение путем зеркального отражения одного из битных значений с bitset.

remainder = bitshift(message,divisorDegree);
remainder = bitor(remainder,CRC_check_value);
remainder = bitset(remainder,6);
dec2bin(remainder)
ans = 
'1101100111011110110'

Выполните операцию деления CRC и затем проверяйте, является ли результатом нуль.

for k = 1:messageLength
    if bitget(remainder,messageLength+divisorDegree)
        remainder = bitxor(remainder,divisor);
    end
    remainder = bitshift(remainder,1);
end
if remainder == 0
    disp('Message is error free.')
else
    disp('Message contains errors.')
end
Message contains errors.

Ссылки

[1] Sklar, Бернард. Цифровая связь: основные принципы и приложения. Englewood Cliffs, NJ: Prentice Hall, 1988.

[2] Ивовый прут, системы контроля ошибок Стивена Б. для цифровой связи и устройства хранения данных. Верхний Сэддл-Ривер, NJ: Prentice Hall, 1995.

Смотрите также

|

Похожие темы