В этом примере показано, как выполнить контроль циклическим избыточным кодом (CRC) на битах номера. CRCs используются, чтобы обнаружить ошибки в передаче данных в цифровых системах. Когда часть данных отправляется, короткое контрольное число присоединено к нему. Контрольное число получено полиномиальным делением с битами в данных. Когда данные получены, полиномиальное деление повторяется, и результат по сравнению с контрольным числом. Если результаты отличаются, то данные были повреждены во время передачи.
Начните с 16-битного двоичного числа, которое является сообщением, которое будет передано:
1101100111011010
Чтобы получить контрольное число, разделите этот номер на полином . Можно представлять этот полином его коэффициентами: 1111
.
Деление выполняется на шагах, и после каждого шага, полиномиальный делитель выравнивается с крайним левым 1 в номере. Поскольку результат деления на четыре полинома термина имеет три бита (в общем делении на полином длины производит контрольное число длины ), добавьте номер с 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.