Рубрики

Циклическое резервирование и подразделение по модулю-2

CRC или Cyclic Redundancy Check — это метод обнаружения случайных изменений / ошибок в канале связи.

CRC использует полином генератора, который доступен как на стороне отправителя, так и на стороне получателя. Пример полинома генератора имеет вид, подобный x 3 + x + 1. Этот полином генератора представляет ключ 1011. Другой пример — x 2 + 1, который представляет ключ 101.

n : Number of bits in data to be sent 
    from sender side.  
k : Number of bits in the key obtained 
    from generator polynomial. 


Сторона отправителя (Генерация закодированных данных на основе данных и полинома генератора (или ключа)):

  1. Сначала двоичные данные дополняются добавлением нулей k-1 в конце данных.
  2. Используйте двоичное деление по модулю-2, чтобы разделить двоичные данные по ключу и сохранить остаток от деления.
  3. Добавить остаток в конце данных, чтобы сформировать закодированные данные и отправить тот же
  4. ,

      Сторона получателя (проверьте, есть ли ошибки при передаче)
      Снова выполните деление по модулю-2, и если остаток равен 0, то ошибок нет.

      В этой статье мы сосредоточимся только на поиске остатка, то есть контрольного слова и кодового слова.

      Подразделение по модулю 2:
      Процесс двоичного деления по модулю-2 такой же, как и при обычном делении, которое мы используем для десятичных чисел. Просто вместо вычитания мы используем XOR здесь.

  • На каждом шаге копия делителя (или данных) XORed с k битами дивиденда (или ключа).
  • Результатом операции XOR (остаток) является (n-1) бит, который используется для следующего шага после удаления 1 дополнительного бита, чтобы сделать его длиной n бит.
  • Когда не осталось битов, которые можно опустить, мы получаем результат. Остаток (n-1) -бита, который добавляется на стороне отправителя.

Иллюстрация:

Пример 1 (нет ошибок при передаче):

Data word to be sent - 100100
Key - 1101 [ Or generator polynomial x3 + x2 + 1]

Sender Side:

Therefore, the remainder is 001 and hence the encoded 
data sent is 100100001.

Receiver Side:
Code word received at the receiver side  100100001

Therefore, the remainder is all zeros. Hence, the
data received has no error. 

Пример 2: (ошибка при передаче)

Data word to be sent - 100100
Key - 1101

Sender Side:

Therefore, the remainder is 001 and hence the 
code word sent is 100100001.

Receiver Side
Let there be error in transmission media
Code word received at the receiver side - 100000001

Since the remainder is not all zeroes, the error is detected at the receiver side.

Реализация

Ниже приведена реализация Python для генерации кодового слова из заданных двоичных данных и ключа.

# Возвращает XOR для 'a' и 'b'
# (оба одинаковой длины)

def xor(a, b):

  

    # инициализировать результат

    result = []

  

    # Обходить все биты, если биты

    # то же самое, тогда XOR равен 0, иначе 1

    for i in range(1, len(b)):

        if a[i] == b[i]:

            result.append('0')

        else:

            result.append('1')

  

    return ''.join(result)

  

  
# Выполняет деление по модулю-2

def mod2div(divident, divisor):

  

    # Количество битов, которые будут XORed за один раз.

    pick = len(divisor)

  

    # Нарезка делителя на соответствующую

    # длина для определенного шага

    tmp = divident[0 : pick]

  

    while pick < len(divident):

  

        if tmp[0] == '1':

  

            # заменить делитель на результат

            № XOR и потяните 1 бит вниз

            tmp = xor(divisor, tmp) + divident[pick]

  

        else:   # Если крайний левый бит равен 0

            # Если самый левый бит дивиденда (или

            (часть, используемая на каждом шаге) равна 0, шаг не может

            # использовать обычный делитель; нам нужно использовать

            # делитель всех нулей.

            tmp = xor('0'*pick, tmp) + divident[pick]

  

        # инкремент выбора, чтобы двигаться дальше

        pick += 1

  

    # Для последних n бит, мы должны выполнить это

    # обычно, так как увеличенное значение пика вызовет

    # Индекс за пределами.

    if tmp[0] == '1':

        tmp = xor(divisor, tmp)

    else:

        tmp = xor('0'*pick, tmp)

  

    checkword = tmp

    return checkword

  
# Функция, используемая на стороне отправителя для кодирования
# данные путем добавления остатка от модульного деления
# в конце данных.

def encodeData(data, key):

  

    l_key = len(key)

  

    # Добавляет ноль-1 нулей в конце данных

    appended_data = data + '0'*(l_key-1)

    remainder = mod2div(appended_data, key)

  

    # Добавить остаток в исходных данных

    codeword = data + remainder

    print("Remainder : ", remainder)

    print("Encoded Data (Data + Remainder) : ",

          codeword)

  
# Код драйвера

data = "100100"

key = "1101"

encodeData(data, key)

Выход:

 Остаток: 001
Кодированные данные (данные + остаток): 100100001

Обратите внимание, что CRC в основном разработан и используется для защиты от распространенных ошибок в каналах связи и НЕ подходит для защиты от преднамеренного изменения данных (см. Причины здесь )

Ссылки:
https://en.wikipedia.org/wiki/Cyclic_redundancy_check

Эта статья предоставлена Джей Патель . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Циклическое резервирование и подразделение по модулю-2

0.00 (0%) 0 votes