데이터의 비트열을 다항식으로 보고 생성 다항식으로 나눈 나머지를 덧붙여 보내고, 수신 측이 같은 계산을 다시 하여 오류를 검출하는 방식. 이더넷, PCI Express, USB, 파일 형식 등에서 널리 사용된다.
일본어 명칭: CRC(巡回冗長検査)
CRC(순환 중복 검사)은(는) 정보 이론과 부호의 기초, 논리 회로, I/O 인터페이스와 버스 등 3개 분야의 연습 문제 8개에 나와요.
분야: I/O 인터페이스와 버스
CRC는 데이터의 비트를 모듈로 2 연산에서의 다항식의 계수로 보고, 생성 다항식으로 나눈 나머지를 구합니다. 모듈로 2 연산에서는 덧셈도 뺄셈도 XOR이므로, 나눗셈은 '맨 앞 비트가 1이면 생성 다항식을 XOR하고 한 자리 옮긴다'의 반복이 됩니다. w비트 CRC에서는 데이터 뒤에 0을 w개 붙여 구한 w비트의 나머지를 데이터와 함께 보내고, 수신 측은 같은 계산을 다시 하여 일치하는지 확인합니다. 실제 규격에서는 초깃값, 바이트마다의 비트 반전, 마지막 XOR 같은 약속이 더해집니다.
w비트 CRC는 길이 w 이하의 버스트 오류를 모두 검출하며, 그 밖의 무작위 오류를 놓칠 확률은 대략 2⁻ʷ입니다. 다만 오류를 검출할 뿐 정정은 할 수 없으므로, 시스템은 재전송으로 복구합니다. CRC는 이더넷의 FCS(CRC-32), PCI Express의 패킷, USB, CAN 버스, 스토리지의 명령, ZIP이나 PNG 같은 파일 형식에서 사용되며, 하드웨어에서는 플립플롭과 XOR 게이트로 된 선형 피드백 시프트 레지스터로 계산할 수 있습니다.
정답: A. 001
1101000을 1011로 나눕니다. 앞의 1101과 1011의 배타적 논리합은 0110, 다음 비트를 내린 1100과 1011의 배타적 논리합은 0111, 1110과 1011에서는 0101, 마지막으로 1010과 1011에서는 0001이 되어 나머지는 001입니다. 보내는 것은 1101001이며, 수신 측은 1011로 나눈 나머지가 0이면 오류가 없다고 판단합니다.
정답: B. 길이가 r비트 이하인 버스트 오류(연속된 범위에 들어가는 오류)는 모두 검출할 수 있다
오류 패턴을 다항식 E(x)로 나타내면, CRC로 검출할 수 없는 것은 E(x)가 생성 다항식 G(x)로 나누어떨어질 때뿐입니다. 길이 r 이하의 버스트 오류는 x^i × B(x)(B(x)는 차수가 r − 1 이하이고 상수항이 1)로 쓸 수 있으며, 상수항이 1인 r차 G(x)로는 나누어떨어지지 않으므로 반드시 검출할 수 있습니다. 한편 G(x) 그 자체의 형태의 오류처럼 나누어떨어지는 패턴은 검출할 수 없습니다. CRC는 주로 오류 검출에 사용되며, 오류가 있으면 데이터를 다시 보내 달라고 합니다.
체크섬은 바이트를 더하는 등의 간단한 연산을 사용하므로 순서가 바뀐 데이터나 서로 상쇄되는 오류를 놓치기 쉽지만, CRC는 다항식의 나눗셈에 기반하여 비트의 위치를 구별하며 버스트 오류를 확실히 잡아냅니다.
일반적으로는 할 수 없습니다. CRC는 오류가 있었는지는 검출하지만 어느 비트가 틀렸는지는 알 수 없으므로, 정정이 필요한 메모리에서는 해밍 부호 같은 ECC를 사용합니다.
오류 패턴을 다항식 E(x)로 나타내면, CRC로 검출할 수 없는 것은 E(x)가 생성 다항식 G(x)로 나누어떨어질 때뿐입니다.
생성 다항식의 차수가 r(검사 비트가 r비트)이고 상수항이 1인 CRC의 성질로 올바른 것은?반가산기의 합, 비교 회로(일치 검출은 XNOR), 패리티 계산, 암호의 스트림 암호와 CRC 계산 등 용도가 넓은 게이트입니다.
2입력 XOR(배타적 논리합) 게이트의 출력이 1이 되는 것은 언제입니까?XOR와 플립플롭만으로 만들 수 있으므로 내장 테스트(BIST)의 패턴 생성과 결과 압축, 이더넷 등의 CRC 계산, 신호를 평균화하여 전자기 노이즈를 줄이는 스크램블러에 사용됩니다.
시프트 레지스터의 일부 출력의 XOR를 입력으로 되돌리는 선형 피드백 시프트 레지스터(LFSR)의 대표적인…CRC에서는 비트의 위치에 따라 나눗셈의 나머지에 미치는 영향이 달라지므로, 이러한 뒤바뀜도 많은 경우에 검출할 수 있습니다.
데이터를 1바이트씩 더하여, 합의 하위 8비트를 검사값(체크섬)으로 붙여 보낸다. 이 검사로 검출할 수 없…ARQ는 CRC 등으로 오류를 검출하고, 받지 못했다는 것을 송신 측에 알려 다시 보내 달라고 하는 방식으로, 되돌아오는 채널이 필요하며 재전송하는 만큼 지연됩니다.
통신에서 오류에 대처하는 방식인 ARQ(자동 재전송 요구)와 FEC(순방향 오류 정정)의 설명으로 올바른 …PCI Express 패리티 비트(Parity Bit) 시프트 레지스터(Shift Register) 플립플롭(flip-flop) BIST(내장 자체 테스트) 순방향 오류 정정(FEC) 128b/130b 인코딩 8b/10b 부호화 네트워크 온 칩(Network-on-Chip) 루트 콤플렉스(Root Complex)