Levent Ozturk

ONLINE CRC BCH CALCULATOR - CODE GENERATOR

This online tool provides the code to calculate CRC (cyclic redundancy check), Scrambler or LFSR ( Linear feedback shift register). The generated code output may be used for Forward Error correction, Block codes and convolutional codes, Gold code generators. This page will calculate the crc lfsr coefficients and will generate Verilog RTL code or C source code. The online code generator can also generate code for convolutional polynomials.
Supported Structures / Algorithms
  • CRC (including BCH)
    CRC
    Example CRC implementaton for x6 + x3 + x1 + 1
    CRCCRCCRCCRCCRCCRCCRCCRCCRCCRCCRCCRCCRC
  • Fibonacci LFSR
  • Galois LFSR
  • Additive Scrambler
  • Multiplicative Scrambler
  • Multiplicative Descrambler
Supported Languages / Output Types
  • Verilog Module
  • VHDL Module
  • C++ Class
  • C Function
  • Java Class
  • Perl Subroutine
  • PHP Function
  • Javascript Function

This tool should solve all your problems (except acne). I tried to make this tool as flexible and understandable as possible. If you still need help using the tool or generating s specialised structure, contact me. This tool generates a code that calculates LFSRs and derivative products. I also have a tool to generate a tool to generate code to calculate LFSR, and CRC which means you can have a module that can calculate any CRC polynomial on the fly. It is not resource friendly but can be very useful in certain cases. Contact me if you are interested. You may also check my other free tools here
I use this to generate the Verilog RTL functions and debug CRC outputs. It helps verifying the overall product. I hope it helps to you too. Enjoy...

Configure
Structure
?
Structure
Select the structure to be generated.
Select one of CRC (including BCH), Additive Scrambler, Multiplicative Scrambler, Multiplicative Descrambler,
Fibonacci LFSR, Galois LFSR.
:
Polynomial
?
Polynomial
Select a predefined standard polynomials from the list, build in the table, or type your polynomial manually below.

The coefficients can be entered in the binary or hexadecimal format. The coefficients should be in GF(2) or GF(16).

The polynomial can be entered in (MSB to LSB) or (LSB to MSB) order.

Despite the common practice the highest order xn should be included.
For example CRC-16 CCITT (0x1021) should be entered as 0x11021.
Maximum polynomial length is x199.

If the final polynomial is convolution of multiple polynomial such as BCH or Reed-Solomon,
seperate each polynomial with a comma character.

Example:
For polynomial x16 + x15 + x2 + 1 enter 10100000000000011
For polynomials x7 + x4 + x1 + 1 and x8 + x6 + x3 + 1 enter 11001001,100100101
The polynomials will be convolved in GF(2).
The convolved polynomial to be processed will be: x15 + x13 + x12 + x4 + 1
:		 or or enter below
Tap direction
This option determines how will the entered value be interpreted. It is for convenience.
Changing this field has the same affect as flipping the input polynomial taps.
It also allows entering polynomial with negative ordered terms.
Note that poynomials with negative ordered terms can be converted to positive ordered terms
by dividing the negative terms with the highest absolute order.
The resulting positive orderd terms poynomial will have the identical implementation

If not selected (X0 to X-n) order will be used.

Left most bit - Right most bitDescription
X0 to X-n
X0 to Xn
X-n to X0The negative highest-order terms correspond to the most significant bits,
while the least significant bit represents the X0 term.

Xn to X0The positive highest-order terms correspond to the most significant bits,
while the least significant bit represents the X0 term.
Initialise
?
Initial value of the polynomial
Initial value of the polynomial (also called seed).

Should be in binary format.

a0 is LSB (right most bit)

Number of initialisation bits should be equal to the polynomial length.
For example x3 + x1 + 1 initialisation value may be 0111 or 0101.
MSB of initialisation value is ignored but must be there.

Excess amount of bits will be removed form the right.
:
Data width
?
Parallel Processing Input Data Width
This field determines the input data width of the generated CRC module.
This field determines the input and output width for Scrambler, Descrambler, LFSR but CRC.
The output bit width is always polynomial width for CRC.

This field determines the number of bits to be processed (consumed/used/required) or number of shifts (clocks/iterations/steps) to occur
in every Hardware clock/Software loop (Parallelization).

Supported data widths are 1 - 63. If you need wider data support, contact me.

For Software functions, data stream is sliced into chunks starting from Stream[0] char
where each chunk contains number of bits determined by the data width field.
Then MSB-LSB is applied to the sliced chunks.

For Hardware modules, data stream is fed to the module as slices that contains bits determined by the data width field.
The user has to slice the data stream into slices.

:
Process Direction
Process direction
If the data width is set to be greater than 1, input data bits are processed
in the order selected by this field. I deliberately avoided using MSB/LSB,
left most/right most, endianness terminology to prevent confusion (including myself).

The generated module will simply accept input data as an array of bits (for SW) or a register
(for HW) and array/register index has no ambiguity regardless of the language or HW/SW.

This field affects both calculator code generation and online calculation as it determines the data input
direction of the core calculator code.
For online calculation, there is an additional filed that can select how the actual input stream
is sliced and fed to the core calculator code.
Generate Code
Speed
?
Speed (Hardware structure)
The generated RTL is added register stages to achieve higher clock frequency.
Help increase fmax. Increase latency by 1 clock. Clock budget (throughput) remains the same.

If speed is checked, data will be pre xored to reduce the number of logic levels to achieve higher a clock frequency.
This will increase the module latency by one clock.
The module is still capable of processing data every clock.
:
Output
?
Output Language
Type of the code to be generated.

HW codes are optimized. SW codes are not optimized yet.

SW codes are implemented straight forward.
C,C++ and Java codes might be rewritten more efficiently.
:
Calculate Output
Input Data
?
Input data
Data stream that the selected poylnomial be applied to generate a CRC result.

If the LFSR is selected, the input data is ignored.
The result represents the value generated by the LFSR after one pass.

If the data width is set to be greater than 2, then the input data is processed in data width chunks
and the input data must be multiples of the data width.

Input data can be entered in binary, decimal or hexadecimal format.

Additionally before processing the input data, the input data can be manipulated for convenience.
After manipulation of the input data, it is processed in the chunks of data width
the manuplation order is:
First input data format is applied.
If hex, each nibble (digit) is converted to 4bit binary. If ascii, each character is converted to 8bit binary.
Then Input data SB is applied. If LSB is selected process starts from the right most bit of input data.
Then flip operation is applied. Each flip occurs within the flip size selected.
Then the resulting input data is split into data width chunnks.
Then data width MSB is applied and the final data is fed to CRC engine.
Processing order within the chunks are still determined by the input data chunk order.
Verbose Format
Stream Manuplation
bit/byte: Each byte in the stream is bit reversed within itself. Bytes remain in the same position in the stream. 00010010 00110100 => 01001000 00101100
bit/32Bit: Each 32 bit in the stream is bit reversed within itself. 32bit blocks remain in the same position in the stream.
Exact: Input stream is processed as is. Default is from Stream[0] to stream[n]
Bit/byte: Forgot why I put this option here. Will explain when I remember.
Bit/32bit: Forgot why I put this option here. Will explain when I remember.
Byte/32 bit: Forgot why I put this option here. Will explain when I remember.
Byte flip: Input stream is reversed keeping each byte value in the stream same. First byte becomes the last byte. 00010010 00110100 => 00110100 00010010
Bit flip: Input stream is reversed. Stream[0] becomes stream[n].
Output Format
Calculate CRC
Calculate the selected CRC of the input data
Calculated CRC:

Common CRC Polynomial functions

Name Hex Form
(right most bit is x0)		 Polynomial Form Initialization (Seed) Test Vector CRC
CRC-4
Interlaken 0x x4 + x1 + 1
CRC-5
USB 0x105 x5 + x2 + 1
EPC 0x109 x5 + x3 + 1001001
CRC-16
Bisync, Modbus, USB, ANSI X3.28, SIA DC-07, CRC-16 ANSI 0x18005 x16 + x15 + x2 + 1
CRC-CCITT 0x11021 x16 + x12 + x5 + 1 0xFFFF0xB1E4
CRC-DNP
DNP, IEC 870, M-Bus		 0x13D65 x16 + x13 + x12 + x11 + x10 + x8 + x6 + x5 + x2 + 1
CRC-24
Interlaken 0x1328B63 x24 + x21 + x20 + x17 + x15 + x11 + x9 + x8 + x6 + x5 + x1 + 10xFFFFFF
LTE 24A 0x1864CFB x24 + x23 + x18 + x17 + x14 + x11 + x10 + x7 + x6 + x5 + x4 + x3 + x1 + 1
CRC-30
CDMA 0x6030B9C7 x30 + x29 + x21 + x20 + x15 + x13 + x12 + x11 + x8 + x7
+ x6 + x2 + x1 + 1
CRC-32
Interlaken 0x x32 + x28 + x27 + x26 + x25 + x23 + x22 + x20 + x19 + x18
+ x14 + x13 + x11 + x10 + x9 + x8 + x6 + 1
(HDLC, ANSI X3.66, ITU-T V.42, Ethernet, IEEE 802.3, Serial ATA, MPEG-2, PKZIP, Gzip, Bzip2, PNG, DVB-S2 GSE) 0x104C11DB7 x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7
+ x5 + x4 + x2 + x1 + 1
CRC-40
GSM 0x10004820009 x40 + x26 + x23 + x17 + x3 + 1
Scrambler
Interlaken Scrambler (?Add Galois) 0x x58 + x39 + 1Any number except all 0
PCI 3.0 Scrambler (Add Galois) 0x210125 x23 + x21 + x16 + x8 + x5 + x2 + 1
PCI 2.0, USB3.0 Scrambler (Add Galois) 0x1039 x16 + x5 + x4 + x3 + 1
OTU4 Scrambler 0x1100B x16 + x12 + x3 + x1 + 1
64b/66b Scrambler (Mult Fib) 0x4000000001 x59 + x38 + 1
DVB-S2 BB Header Scrambler (Add Fib) **There is an inconsistency in the convention of polynomial definition 0xC001 x15 + x14 + 1 (Must be x-15 + x-14 + 1 to match the structure described)
V.34 Scrambler (Mult Fib) 0x840001 x-23 + x-18 + 1
V.27 Scrambler (Mult Fib) 0xc1 x-7 + x-6 + 1
Test Vector CRC is the output CRC value for the input data stream of 0x12345670


There are two types of Shift Register (SR) structures:Galois and Fibonacci. These are the base of all other structures such as LFSR, CRC, Scrambler, Descrambler, PN Sequences, Gold Code Generators, Pseudo Random Bit Sequences (PRBS).
These two SR structures are called Linear Feedback Shift Registers (LFSR) if their tap coefficients are only 1 or 0. If any of the tap coefficient is a value other than 1 or 0, they become Non Linear Shift registers.
Below is the realisation in Galois and Fibonacci structures for the same feedback configuration.
The number of taps and feedback points are chosen the same for the purpose of easy comparision.
Based on same taps and feedback points, notice that polynomials and the functionality are different for Galois and Fibonacci structures.
Galois structure taps always increment from left to right and Fibonacci taps always increment from right to left. Fibonacci feedback tap notation decrements in line with the shift direction. Represantation of polynomilas can be resolved based on this rule.
Example

Galois Structure

Polynomial:x6 + x3 + x1 + 1
CRCCRCCRCCRCCRCCRCCRCCRCCRCCRCCRCCRC
CRC:
No padding needed		CRCCRCCRCCRCCRCCRCCRCCRCCRCCRCCRCCRCCRC
CRC:
Padding needed		CRCCRCCRCCRCCRCCRCCRCCRCCRCCRCCRCCRC
Galois LFSR: Galois LFSRGalois LFSRGalois LFSRGalois LFSRGalois LFSRGalois LFSRGalois LFSRGalois LFSRGalois LFSRGalois LFSRGalois LFSRGalois LFSRGalois LFSR

Fibonacci Structure

Polynomial:x-6 + x-3 + x-1 + 1 or
(1 + x3 + x5 + x6)x-6
PolynomialPolynomialPolynomialPolynomialPolynomialPolynomialPolynomialPolynomialPolynomialPolynomialPolynomialPolynomial
PolynomialPolynomialPolynomialPolynomialPolynomialPolynomialPolynomialPolynomialPolynomialPolynomialPolynomialPolynomial
Fibonacci LFSR: Fibonacci LFSRFibonacci LFSRFibonacci LFSRFibonacci LFSRFibonacci LFSRFibonacci LFSRFibonacci LFSRFibonacci LFSRFibonacci LFSRFibonacci LFSRFibonacci LFSRFibonacci LFSRFibonacci LFSR
Additive Scrambler (Descrambler): Additive ScramblerAdditive ScramblerAdditive ScramblerAdditive ScramblerAdditive ScramblerAdditive ScramblerAdditive ScramblerAdditive ScramblerAdditive ScramblerAdditive ScramblerAdditive ScramblerAdditive Scrambler
Multiplicative Scrambler: Multiplicative ScramblerMultiplicative ScramblerMultiplicative ScramblerMultiplicative ScramblerMultiplicative ScramblerMultiplicative ScramblerMultiplicative ScramblerMultiplicative ScramblerMultiplicative ScramblerMultiplicative ScramblerMultiplicative ScramblerMultiplicative Scrambler
Multiplicative Descrambler: Multiplicative DescramblerMultiplicative DescramblerMultiplicative DescramblerMultiplicative DescramblerMultiplicative DescramblerMultiplicative DescramblerMultiplicative DescramblerMultiplicative DescramblerMultiplicative DescramblerMultiplicative DescramblerMultiplicative DescramblerMultiplicative Descrambler
  • Note that Galois LFSR counts in reverse order of the Fibonacci LFSR for the same polynomial. To switch between Galois and Fibonacci structure for the identical counter, negate (flip, mirror over X0) all the tap signs. this will be an identical counter but possibly with a different start point.
  • For the positive taps equalent of a negative taps polynomial (which will result the identical counter), divide the polynomial by the absolute highest order.
    (x-6 + x-3 + x-1 + 1)/x-6 = (1 + x3 + x5 + x6)
    Galois (x-6 + x-3 + x-1 + 1) = Galois (1 + x3 + x5 + x6) ≠ Galois (x6 + x3 + x1 + 1)

    Fibonacci (x-6 + x-3 + x-1 + 1) = Fibonacci (1 + x3 + x5 + x6) ≠ Fibonacci (x6 + x3 + x1 + 1)

    Galois (x6 + x3 + x1 + 1) = Fibonacci (x-6 + x-3 + x-1 + 1)
In the padding needed CRC circuit, after processing the message, 5 (the polynomial order) 0-bits would have to be fed in. Then the CRC register would have the desired checksum.
The scramblers are implemented in Fibonacci form. Galois form scrambler/descrambler code can also be extracted from existing options.
Galois versus Fibonacci
Polynomial x3 + x1 + 1
= x3(x-3 + x-2 + 1)		 | x-3 + x-1 + 1
= x-3(x3 + x2 + 1)
Galois
Fibonacci
Structure

G

G

F

G

F

F
Initialize 001 101 001 001 001 101
Count
 001 101 001 001 001 101
110 100 100 010 100 110
011 010 110 100 010 111
111 001 111 101 101 011
101 110 011 111 110 001
100 011 101 011 111 100
010 111 010 110 011 010
RepeatingRepeating
001 101 001 001 001 101
110 100 100 010 100 110
011 010 110 100 010 111
111 001 111 101 101 011
101 110 011 111 110 001
Red is randomly selected syncronus point for each counter.
Blue counters count the same direction, same order, different offset.
Yellow counters count the same direction, same order, different offset.
Blue and yellow count in opposite order. Generate same numbers in reverse direction.
Notice the polynomial, structure, initialization and count order relation.
Also notice time offset between the counters for the same initial point.
Also notice that any tap can be picked as output. All the taps count the same only differ with a starting offset.
All the material listed and linked at this World Wide Web domain are strictly private property and copyrighted. © Copyright -∞-∞ Levent Ozturk. All rights reserved. Reproduction or use of any material, documents and related graphics and any other material from this World Wide Web server is strictly prohibited. Site Map