Altera Devices July 1995, ver. Application Note Redundant en

The Datasheet Archive - 100 Million Datasheets from 7500 Manufacturers.

Altera Devices July 1995, ver. Application Note Redundant en

Datasheet Thumbnail

Top Searches for this datasheet

Implementing CRCCs
Altera Devices
July 1995, ver. Application Note
Redundant encoding method error detection that spreads information across more bits than original data. more redundant bits use, greater chance that will detect transmission errors. example, 16-bit increase data record length misses error 65,536, while 32-bit increase misses only error over billion. Although these odds favorable, undetectable errors still occur. nature common errors varies depending transmission storage medium, undetectable errors caused occasional isolated changed bits short bursts multiple changed bits. minimize undetectable errors, distribute data that less likely that transmission errors will result valid encoding alternate data. Cyclic redundancy codes (CRCs) favored type redundant encoding. Cyclic redundancy code checkers (CRCCs) check differences between transmitted data original data. Data transmission applications CRCCs extensively. example, Asynchronous Transfer Mode (ATM) specification requires CRCC that implemented across entire payload ensure data integrity. CRCCs particularly effective reasons:
They provide excellent protection against common errors, such burst errors where consecutive bits data stream corrupted during transmission. original data first part transmission, which makes systems that CRCCs easy understand implement.
When CRCC verify frame data, frame treated very large binary number, which then divided generator number. This division produces remainder, which transmitted along with data. receiving end, data divided same generator number remainder compared sent data frame. remainders different, then error occurred during data transmission.
Altera Corporation
A-AN-049-01
Implementing CRCCs Altera Devices
Creating CRCCs
general, digital logic does implement division very large numbers efficiently. Consequently, binary information must converted into more appropriate form before CRCCs used. string bits verified represented coefficients large polynomial, rather than large binary number, shown following example: 1,0001,0000,0010,0001 make calculations easier implement, arithmetic cast binary algebraic field. arithmetic implemented modulo with carry, i.e., addition subtraction identical (implemented XOR). Multiplication performed with function, division binary field's single non-zero element, leaves dividend unchanged. this system, remainder polynomial degree more than bits long. Therefore, even though polynomials order have terms (including X0), remainder contained within bits (X15 through X0). When implementing CRCCs, both original data generator number must represented polynomials. generator number therefore called generator polynomial. polynomial that represents original data multiplied where degree generator polynomial (i.e., length CRC). This operation shifts data left bits. resulting polynomial allow data polynomial replacing last bits (which have become with CRC. Since addition subtraction equivalent, this operation also produces polynomial that evenly divisible generator polynomial. Therefore, when data polynomial plus divided generator polynomial receiving system, remainder error-free transmission always summary, data multiplied divided generator polynomial quotient then discarded, remainder added dividend following equation: receiving end, first part transmitted information original data second part (the last bits) remainder This entire quantity divided same generator polynomial quotient discarded. remainder this division always there errors transmitted data.
Altera Corporation
Implementing CRCCs Altera Devices
Error Detection
Generally, CRCCs detect following types errors:
Single-bit errors Two-bit errors Three-bit other odd-number-bit errors Burst errors that less than equal length Most burst errors that greater than length
types errors that CRCC detects depends generator polynomial. Table shows several common generator polynomials various applications.
Table Common Generator Polynomials
Generator Name
SDLC (CCITT) SDLC Reverse CRC-16 CRC-16 Reverse CRC-12 Ethernet
Polynomial
Different generator polynomials have different error-detection capabilities. achieve optimum results, must generator polynomial that effectively detects corrects expected transmission errors. Alternatively, standard generator polynomial that appropriate particular transmission medium.
Serial Computation
Typically, calculations implemented with linear-feedback shift registers (LFSRs). LFSRs method that yields same results subtract shift division process when subtraction performed without carry function. affect subtract shift division time, shift through examine each original frame data (i.e., dividend). first value divisor high-order subtracted (XORed) from dividend. That dividend bit, which unnecessary generated, zero subtraction. lower order bits divisor cannot subtracted yet, because corresponding divisor bits have been shifted
Altera Corporation
Implementing CRCCs Altera Devices
Figure shows Consultative Committee International Telegraph Telephone (CCITT) CRC-16 generator computed serially. quotient (XOR16) back subtracted from appropriate taps shift register (XOR12, XOR5, XOR0). These bits shift forward appear subtracted from next data bit, unless they eliminated coinciding second from earlier later subtraction that back.
Figure LFSR Configuration CCITT CRC-16 Generator (X16
XOR0 Register Register XOR5 Register Register XOR12 Register Register
XOR16 Data
Parallel Computation
serial method works well when data available bit-serial form. However, today's high-speed signal processing systems process data byte, word, double-word (32-bit), larger widths rather than serially. Even telecommunications systems, which transmit data serially, received data encapsulated within VLSI device responsible Clock recovery byte framing. data presented board designer 8-bit frames manageable speed. Therefore, designs high-speed devices require calculated bits time. develop parallel algorithm with LFSR approach. express contents shift register after shifts function initial contents shift register data bits shifted This function created using only operators. Figure shows function that uses CCITT CRC-16 generator polynomial (X16 X0). this example, register contents C[15.0] next data bits D[7.0] used calculate general contents register after shifts. Because register shifts once each input data bit, XOR16 operator produces series terms etc. These terms assigned name where
Altera Corporation
Implementing CRCCs Altera Devices
Figure Register Shifts CCITT CRC-16 Generator (X16
terms line XORed together.
register after shifts
XOR16 Reg0 Reg1 Reg2 Reg3 Reg4 Reg5 Reg6 Reg7 Reg8 Reg9 Reg10 Reg11 Reg12 Reg13 Reg14 Reg15
XOR16
XOR16
XOR16
Shift
Shift
Shift
Shift
Shift
first four shifts, only terms back. fifth shift, register contains M0(from earlier shifts), which will XORed with back, shown following equation: Later shifts have multiple terms back. register contents after shifts shown right.
AHDL Macrofunction
Figure shows excerpt from Altera Hardware Description Language (AHDL) Text Design File (.tdf) that includes logic equations register values after shifts (i.e., byte later).
Altera Corporation
Implementing CRCCs Altera Devices
Figure AHDL Design Excerpt
reg[0] reg[1] reg[2] reg[3] reg[4] reg[5] reg[6] reg[7] dat[0] dat[1] dat[2] dat[3] dat[4] dat[5] dat[6] dat[7]
reg[0].d reg[1].d reg[2].d reg[3].d reg[4].d reg[5].d reg[6].d reg[7].d reg[8].d reg[9].d reg[10].d reg[11].d reg[12].d reg[13].d reg[14].d reg[15].d
reg[8] reg[9] reg[10] reg[11] reg[12] reg[13] reg[14] reg[15]
complete AHDL description CCITT CRC-16 macrofunction available self-extracting file an_049.exe from Altera bulletin board service (BBS) (408) 954-0104 from Altera's site.
calculated before frame data transmitted, then each data byte clocked into macrofunction. Conversely, clocked during each byte transmitted data. After last byte data clocked 16-bit appended data. multiplexer selects byte (REG[7.0]), then selects high byte transmission.
Altera Corporation
Implementing CRCCs Altera Devices
check after data transmission, should clear shift register asserting Clear signal. macrofunction enabled Clock cycle during each byte received data, including bytes calculated transmission appended data frame. After last byte clocked register contains 16-bit transmitted data plus transmitted CRC, shown following equation: there errors transmission, remainder CRC00 signal asserted.
Piecewise CRCC Computation
packet-switching networks (such Anetworks), frame broken into small packets transmission, then reassembled into original long frame after received. frame include that allows CRCC verify integrity entire frame once reassembled. easier generate while frame still original format. more complex transmission protocols, generation require communications processor, which easily become overburdened. avoid need communications processor entirely, compute hardware lower level. However, method cause packets from different frames intermingle, especially receiving end. prevent intermingling frames, compute each packet separately, i.e., piecewise. Once CRCC been executed over packet, interim stored small that indexed channel number. next packet, channel number first determined from header, interim previous channel extracted from loaded into register. packet's data then clocked into CRC. packet, interim next packet stored preparation next packet. Sometimes data path needs delayed bytes allow cycles acquire channel number load previous interim into macrofunction. When last packet frame transmitted, appended data that verified when received. piecewise method adds control logic design. However, this method little effect engine; register must simply loaded with interim previous channel before proceeding with each packet's data.
Altera Corporation
Implementing CRCCs Altera Devices
sample file macrofunction with added load function available self-extracting file an_049.exe from Altera bulletin board service (BBS) (408) 954-0104 from Altera's site.
Each frame's packets must processed same order transmission reception. packets sequence when they received, CRCC indicates error. burst errors also detected reported.
Conclusion
CRCCs efficient method verifying data transmission, especially Aapplications. CRCCs offer protection from common errors without adding extensive logic overhead. either serial parallel computation methods implement CRCCs. applications which data frame segmented mixed with data from other frames, piecewise calculation most effective. Hamming, R.W. Coding Information Theory. Prentice-Hall, 1980. Lee, "Cyclic Code Redundancy." Digital Design, 7/81. Perez, "Byte-wise Calculations." IEEE MICRO, 6/83. Peterson, W.W., Brown, D.T. "Cyclic Codes Error Detection." Proc. IRE, 1/61. Peterson, W.W. Weldon, E.J. Error-Correcting Codes. Press, 1961. Pless, Vera. Introduction Theory Error-Correcting Codes. John Wiley Sons, 1982. Ramabadran, T.V. Gaitonde, S.S. Tutorial Computations." IEEE MICRO, 8/88.
Bibliography
2610 Orchard Parkway Jose, 95134-2020 (408) 894-7000 Applications Hotline: (800) 800-EPLD Customer Marketing: (408) 894-7104 Literature Services: (408) 894-7144
Printed Recycled Paper.
Altera, MAX, MAX+PLUS, FLEX, FLEX Ability registered trademarks Altera Corporation. following trademarks Altera Corporation: MAX+PLUS AHDL. Altera acknowledges trademarks other organizations their respective products services mentioned this document. Altera products marketed under trademarks protected under numerous U.S. foreign patents pending applications, maskwork rights, copyrights. Altera warrants performance semiconductor products current specifications accordance with Altera's standard warranty, reserves right make changes products services time without notice. Altera assumes responsibility liability arising application information, product, service described herein except expressly agreed writing Altera Corporation. Altera customers advised obtain latest version device specifications before relying published information before placing orders products services. U.S. European patents pending. Copyright 1995 Altera Corporation. rights reserved.
Altera Corporation

Altera Devices July 1995, ver. Application Note Redundant en

Top Searches for this datasheet

Other recent searches