# Download: Draft

CYCLIC REDUNDANCY CHECKS IN USB Introduction The USB specification calls for the use of Cyclic Redundancy Checksums (CRC) to protect all non-PID fields in token and data packets from errors during transmission. This paper describes the mathematical basis behind CRC in an intuitive fashion and then explains the specific implementation called for in USB. Perl programs to generate these CRCs are provided and several examples are used to clear up possible ambiguous areas. Two-minute mathematical background The well-known concept of integer division forms the basis for the use of CRCs. When a divid...

Author:
Zoble1980 Shared: 8/19/19

Downloads: 287 Views: 4390

## Content

CYCLIC REDUNDANCY CHECKS IN USB Introduction The USB specification calls for the use of Cyclic Redundancy Checksums (CRC) to protect all non-PID fields in token and data packets from errors during transmission. This paper describes the mathematical basis behind CRC in an intuitive fashion and then explains the specific implementation called for in USB. Perl programs to generate these CRCs are provided and several examples are used to clear up possible ambiguous areas. Two-minute mathematical background The well-known concept of integer division forms the basis for the use of CRCs. When a dividend is divided by a divisor, a quotient and a remainder (which may be 0) result. If the remainder is subtracted from the dividend and this is divided by the divisor, the remainder is always zero. e.g. when 629 is divided by 25, the remainder is 4. If the dividend (629) and the remainder (4) are transmitted from a source to a target, the integrity of the transmission can be verified at the target by recomputing the remainder and verifying that the remainder matches the transmitted remainder. Alternatively, the target could divide the difference between the transmitted dividend and remainder and expect to see a zero remainder if there were no errors. The concept of integer division can also be applied to division of polynomials. (An intuitive way to understand this is by considering that the digits which make up an integer can be considered the coefficients of a polynomial in base 10 e.g. 629 = 6*102 + 2* 101 + 9*100.). A binary bitstream (which is a pattern of 1s and 0s) can be considered to represent the coefficients of a (dividend) polynomial. When this polynomial is divided by a generator (divisor) polynomial (which is another binary bitstream) a remainder polynomial (CRC) will result. The arithmetic is especially simplified if 1 and 0 are considered to be elements of a finite field (the Galois field of order 2 or GF(2)) . The arithmetic is sometimes referred to as modulo 2 arithmetic. For the purposes of CRC computation, it is sufficient to understand that addition and subtraction in this field reduce to simple XOR operations. This is the basis of the technique used for generating and checking CRC for USB packets. CRCs are useful because they are capable of detecting all single and double errors and many multiple errors with a small number of bits. Communications protocols often use two CRCs in a packet - one to protect the header of the packet and another to protect the data portion of the packet. In USB the header of the packet is the PID field. Since this field is only 4 bits long it is protected bya4bit check field derived by simple bitwise inversion of the PID field. This provides adequate single-bit and burst error protection, without requiring CRC generation and checking logic. The ‘data’ portion of a USB packet which is longer is protected by a conventional CRC field. In token packets, the CRC protected region is only 11 bits - soa5bit CRC provides adequate protection and also aligns the packet to a byte boundary. Data packets may have upto 1023 bytes; so a longer (16 bit) CRC is used to protect the data. CRC implementation for USB The USB spec lists two generator polynomials - one for tokens and the other for data packets. The generator polynomial for tokens is x5 + x2 + x0 while the generator polynomial for data packets is x16 + x15 + x2 + x0. Since the remainder is always of smaller degeree than the generator polynomial, the token CRC isa5bit pattern and the data CRC is a 16 bit pattern. An intuitive way to generate the CRC for an input pattern would be to simply divide this pattern by the generator poylnomial. The division can use the same approach used in integer division. If the Most Significant digit/Bit (MSB) of the dividend is a 1, the divisor is subtracted from the dividend to generate a new dividend. In modulo 2 arithmetic, this subtraction is simply a bit-wise XOR. The same step is repeated for the next MSB in sequence through all the bits including the Least Significant Bit (LSB). The remainder at this point is the remainder from dividing the input pattern multiplied by xd by the generator polynomial of degree d (d is 5 for token CRC and 16 for data CRC). The implementation called for in the USB spec differs from the above intuitive approach in three ways which are mathematically insignificant. 1. The implementation starts off with the shift register loaded with all 1s. Without this, leading 0s in front of a packet would not be protected by the CRC generated. Mathematically this is equivalent to adding a scaled constant to the dividend. The scaling is a function of number of bits in the input pattern. At the receiving target, the shift register is likewise primed with 1s. This ensures that the same scaled constant is added to the dividend at the target (assuming no bits are lost in transit). So if no bits are corrupted in transit, the same remainder will be generated at both ends. In equation form the scaling creates the dividend D(x) = x32F(x) + xkL(x) where F(x) is a degree (k-1) polynomial representing the k bits of the data stream and L(x) is a degree (d-1) polynomial with all coefficients equal to one and d is degree of the generator polynomial. 2. The implementation uses commutativity and associativity of the XOR operation to advantage. In the intuitive approach, the new dividend is derived by subtracting the divisor from the dividend. In the implementation, this subtraction is done bit by bit on the dividend by accumulating and shifting the remainder. 3. The remainder is bit-wise inverted before being appended as the checksum to the input pattern. Without this modification, trailing zeros at the end of a packet could not be detected as data transmission errors. Mathematically, this is equivalent to adding a known, constant to the remainder. Again this is mathematically insignificant to the operation of CRC. In equation form, CRC= L(x) + R(x) where R(x) is remainder obtained by dividing D(x) by the generator polynomial G(x). Checking the CRC at the target is the same as generating the CRC on an input pattern which now consists of the original input pattern followed by the inverted remainder. Mathematically, this new polynomial should be perfectly divisible by the generator polynomial except for the residual due to the known constant discussed in item 3 above. (This can be intuitively understood by realizing that the appending of the remainder to the LSB of the dividend is equivalent to subtracting it from the old dividend). In equation form, the transmitted and received data is M(x)=x32F(x) + CRC. When CRC is generated on this pattern M(x), the remainder R’(x) is x32L(x)/G(x) and can be derived from the above equations and some properties of modulo 2 arithmetic. R’(x) is a unique polynomial (i.e. coeffiecients are always the same) since L(x) and G(x) are unique. R’(x) is termed the residue or residual polynomial. For the token generator polynomial, the residual is 01100 (or x4 + x3) ; for the data CRC polynomial the residual is 1000000000001101 ( or x15 + x3 + x2 + x0). Programs for generating CRC While the above sections contain enough information to implement the CRC logic, it is quite easy to get the bit order confused. The following two programs in Perl (crc5 and crc16) can be used for checking the implementation of the token crc and data crc respectively. #! /usr/local/bin/perl ## crc5 nrzstream ## e.g. crc5 1000111 ## nrz stream is sent in left to right order ## generated crc should also be sent out in left to right order sub xor5 { local(@x) = @_[0..4]; local(@y) = @_[5..9]; local(@results5) = (); for($j=0;$j<5;$j++) { if (shift(@x) eq shift(@y)) { push(@results5, '0'); } else { push(@results5, '1'); } } return(@results5[0..4]); } { local($st_data) = $ARGV[0]; local(@G) = ('0','0','1','0','1'); local(@data) = split (//,$st_data); local(@hold) = ('1','1','1','1','1'); if (scalar(@data) > 0) { loop5: while (scalar(@data) > 0) {, $nextb=shift(@data); if (($nextb ne "0") && ($nextb ne "1")) {next loop5} ## comment character if ($nextb eq shift(@hold)) {push(@hold, '0')} else { push(@hold, '0'); @hold = &xor5(@hold,@G); } ## print (@hold); print "\n"; } } ## print (@hold); print "\n"; ## invert shift reg contents to generate crc field for ($i=0;$i<=$#hold;$i++) {if (@hold[$i] eq "1") {print("0")} else { print("1")} } print "\n"; } #! /usr/local/bin/perl ## usage: ## crc16 nrzstream ## nrz stream is sent in left to right order ## generated crc should also be sent out in left to right order sub xor16 { local(@x) = @_[0..15]; local(@y) = @_[16..31]; local(@results16) = (); for($j=0;$j<16;$j++) { if (shift(@x) eq shift(@y)) { push(@results16, '0'); } else { push(@results16, '1'); } } return(@results16[0..15]); } { local($st_data) = $ARGV[0]; local(@G) = ('1','0','0','0','0','0','0','0','0','0','0','0','0','1','0','1'); local(@hold) = ('1','1','1','1','1','1','1','1','1','1','1','1','1','1','1','1'); local(@data) = split (//,$st_data); if (scalar(@data) > 0) { loop16: while (scalar(@data) > 0) { $nextb=shift(@data); if (($nextb ne "0") && ($nextb ne "1")) {next loop16} ## comment character if ($nextb eq shift(@hold)) {push(@hold, '0')} else { push(@hold, '0'); @hold = &xor16(@hold,@G); } } } # print (@hold); print "\n"; ## invert shift reg to generate CRC field for ($i=0;$i<=$#hold;$i++) {if (@hold[$i] eq "1") {print("0")} else { print("1")} } print "\n"; }, Examples of CRC computation To further solidify the understanding of the implementation, the following examples are presented. Consider generating an SOF token with timestamp of 710(hex). CRC5 can be used to generate the CRC on the timestamp with the following results. crc5 00001000111 The timestamp and CRC and EOP (End Of Packet) can be appended to the Sync, PID and PID check fields to generate the NRZ (Non Return to Zero) packet as follows. 00000001101001010000100011110100XX1; In this example the NRZ sync field is 00000001 and the EOP is indicated as XX1 where X indicates a single ended 0. The PID and PID check fields are 0101 and 1010 respectively. Note that bit stuffing and conversion to NRZI (Non Return to Zero Invert) will be performed (described in sec. 7.1.5 and sec. 7.1.6 of the spec) before the packet is transmitted on the USB. Since these operations do not affect the bit order or the CRC generation/checking they are not described in this paper. Examples of SETUP, OUT, IN and SOF tokens (with address, endpoint and timestamp values in hex), the crc5 generation and the resulting NRZ packet are presented below. setup addr 15 endp e crc5 10101000111 00000001101101001010100011110111XX1; out addr 3a endp a crc5 01011100101 00000001100001110101110010111100XX1; in addr 70 endp 4 crc5 00001110010 00000001100101100000111001001110XX1; sof timestamp 001 crc5 10000000000, 00000001101001011000000000010111XX1; Examples of data packets are presented below. DATA0 and DATA1 packets, each with 4 bytes of data (indicated in hex) , the crc16 generation and the resulting NRZ packets are listed respectively below. data0 00 01 02 03 crc16 00000000100000000100000011000000 0000000111000011000000001000000001000000110000001111011101011110XX1; data1 23 45 67 89 crc16 11000100101000101110011010010001 0000000111010010110001001010001011100110100100010111000000111000XX1;]

15

## Similar documents

1 ;*************************************************************************** 2 ;* USBSTACKFORTHEAVRFAMILY3;* 4 ;* File Name :"USBtoRS232.asm" 5 ;* Title :AVR309:USB to UART protocol converter 6 ;* Date :01.02.2004 7 ;* Version :2.8 8 ;* Target MCU :ATmega8 9 ;* AUTHOR :Ing. Igor Cesko 10 ;* Slovak

1 ;*************************************************************************** 2 ;* USBSTACKFORTHEAVRFAMILY3;* 4 ;* File Name :"USB90S2313.asm" 5 ;* Title :AVR309:USB to UART protocol converter (simple - small FIFO) 6 ;* Date :26.01.2004 7 ;* Version :2.2 8 ;* Target MCU :AT90S2313-10 9 ;* AUTHOR :I

AVR309: Software Universal Serial Bus (USB) Features • USB (Universal Serial Bus) protocol implemented in firmware • Supports Low Speed USB (1.5Mbit/s) in accordance with USB2.0 • Implementation runs on very small AVR devices, from 2kBytes and up • Few external components required - One resistor for

8-bit Microcontrollers Application Note AVR270: USB Mouse Demonstration Features • Runs with AT90USB Microcontrollers at 8MHz • USB Low Power Bus Powered Device (less then 100mA) • Supported by any PC running Windows® (98SE or later), Linux® or Mac OS®. • 3Kbytes of Code Required • X, Y Movement, Le

8-bit Microcontroller Application Note Rev. 2547A–AVR–11/03 AVR244: AVR UART as ANSI Terminal Interface Features • Make use of standard terminal software as user interface to your application. • Enables use of a PC keyboard as input and ascii graphic to display status and control information. • Driv

Device Pins A/D PSP Pin Diagram PIC16C63A 28 NO NO PDIP, Windowed CERDIP PIC16C73B 28 YES NO MCLR/VPP 1 40 RB7 PIC16C65B 40 NO YES RA0/AN0 2 39 RB6 RA1/AN1 3 38 RB5 PIC16C74B 40 YES YES RA2/AN2 4 37 RB4 RA3/AN3/VREF 5 36 RB3 RA4/T0CKI 6 35 RB2 Microcontroller Core Features: RA5/SS/AN4 7 34 RB1RE0/RD

PCM2704 and PCM2705 Not Recommended For New Designs PCM2704, PCM2705 PCM2706, PCM2707 Burr-Brown Audio www.ti.com... SLES081F–JUNE 2003–REVISED JANUARY 2009 STEREO AUDIO DAC WITH USB INTERFACE, SINGLE-ENDED HEADPHONE OUTPUT AND S/PDIF OUTPUT 1FEATURES – External ROM Interface (PCM2704/6) 2345• On-Ch

FOREWORD This repair manual has been prepared to provide essential in- formation on body panel repair methods (including cutting and welding operations, but excluding painting) for the TOYOTA YARIS. Applicable models: KSP90 series Applicable models: NCP90, 91 series This manual consists of body repa

MPASM and MPLINK PICmicro® QUICK REFERENCE GUIDE The Embedded Control Solutions Company® MPASM Quick Reference Guide This Quick Reference Guide gives all the instructions, directives, and command line options for the Microchip MPASM Assembler. MPASM Directive Language Summary Directive Description S

M Author: Mark Palmer Microchip Technology Inc. INTRODUCTION The PICmicro™ families of RISC microcontrollers are designed to provide advanced performance and a cost-effective solution for a variety of applications. To address these applications, there is the PIC16CXXX microcontroller family of produ

1NZ-FE ENGINE MECHANICAL – ENGINE EM–1 M ENGINE ON-VEHICLE INSPECTION 1. INSPECT ENGINE COOLANT (See page CO-1) 2. INSPECT ENGINE OIL (See page LU-1) 3. INSPECT BATTERY (See page CH-4) 4. INSPECT AIR CLEANER FILTER ELEMENT SUB- ASSEMBLY (a) Remove the air cleaner filter element sub-assembly. (b) Vis

FOREWORD This wiring diagram manual has been prepared to provide information on the electrical system of the 2007 YARIS. Applicable models: NCP91, 93 Series Refer to the following manuals for additional service specifications and repair procedures for these models: Manual Name Pub. No. 2007 YARIS Re

U340E AUTOMATIC TRANSAXLE – AUTOMATIC TRANSAXLE SYSTEM AX–1 X AUTOMATIC TRANSAXLE SYSTEM PRECAUTION NOTICE: • Perform the RESET MEMORY (AT initialization) when replacing the automatic transaxle assembly, engine assembly or ECM (See page AX-14). • Perform the REGISTRATION (VIN registration) when repl

ON Semiconductor 2N5550 Amplifier Transistors NPN Silicon 2N5551* *ON Semiconductor Preferred Device MAXIMUM RATINGS Rating Symbol 2N5550 2N5551 Unit Collector–Emitter Voltage VCEO 140 160 Vdc Collector–Base Voltage VCBO 160 180 Vdc Emitter–Base Voltage VEBO 6.0 Vdc Collector Current — Continuous IC

GENERAL DESCRIPTION QUICK REFERENCE DATA Glass passivated sensitive gate SYMBOL PARAMETER MAX. UNIT thyristor in a plastic envelope, intended for use in general purpose VDRM, Repetitive peak off-state voltages 200 V switching and phase control VRRM applications. This device is intended IT(AV) Averag

Order this document SEMICONDUCTOR TECHNICAL DATA by 2N3903/D NPN Silicon *Motorola Preferred Device COLLECTOR BASE EMITTER 1 MAXIMUM RATINGS Rating Symbol Value Unit CASE 29–04, STYLE 1 TO–92 (TO–226AA) Collector–Emitter Voltage VCEO 40 Vdc Collector–Base Voltage VCBO 60 Vdc Emitter–Base Voltage VEB

DISCRETE SEMICONDUCTORS DATA SHEET M3D125 2N2222; 2N2222A NPN switching transistors Product specification 1997 May 29 Supersedes data of September 1994 File under Discrete Semiconductors, SC04 FEATURES PINNING • High current (max. 800 mA) PIN DESCRIPTION • Low voltage (max. 40 V). 1 emitter 2 base A

Philips Semiconductors Small-signal Transistors Selection guide V TYPE CEO IC Ptot fhhTPNP PACKAGE max. max. max. FE FE min. PAGE NUMBER min. max. COMPL. (V) (mA) (mW) (MHz) BC846 SOT23 65 100 250 110 450 100 BC856 305 BC846A SOT23 65 100 250 110 220 100 BC856A 305 BC846AT SC-75 65 100 150 110 220 1

Philips Semiconductors Small-signal Transistors Selection guide SURFACE-MOUNT DEVICES NPN GENERAL PURPOSE LOW-POWER TRANSISTORSVIPfTYPE CEO C tothhTPNP PACKAGE max. max. max. FE FE min. PAGE NUMBER min. max. COMPL. (V) (mA) (mW) (MHz) 2PC4081 SC-70 40 100 200 120 560 100 2PA1576 210 2PC4081Q SC-70 4

Philips Semiconductors Small-signal Transistors Selection guide LEADED DEVICES (continued) NPN HIGH-VOLTAGE POWER TRANSISTORSVIPfTYPE CEO C tothhTPACKAGE max. max. max. FE FE PNP min. PAGE NUMBER min. max. COMPL. (V) (mA) (mW) (MHz) BF419 TO-126 250 300 6000 45 typ. >45 90 – 532 BF457 TO-126 160 100

DISCRETE SEMICONDUCTORS DATA SHEET handbook, halfpage M3D114 1PS302 High-speed double diode Product specification 1996 Apr 03 File under Discrete Semiconductors, SC01 FEATURES DESCRIPTION PINNING • Very small plastic SMD package The 1PS302 consists of two PIN DESCRIPTION • High switching speed: max.

DISCRETE SEMICONDUCTORS DATA SHEET handbook, halfpage M3D114 1PS301 High-speed double diode Product specification 1996 Apr 03 File under Discrete Semiconductors, SC01 FEATURES DESCRIPTION PINNING • Very small plastic SMD package The 1PS301 consists of two PIN DESCRIPTION • High switching speed: max.

DISCRETE SEMICONDUCTORS DATA SHEET handbook, halfpage M3D114 1PS300 High-speed double diode Product specification 1996 Apr 03 File under Discrete Semiconductors, SC01 FEATURES DESCRIPTION PINNING • Very small plastic SMD package The 1PS300 consists of two PIN DESCRIPTION • High switching speed: max.