Comparison of Reed-SolomonCodec ImplementationsComparison of Reed-SolomonCodec ImplementationsHeather Bowers & Hui ZhangCS252 Project, Fall 1996http://infopad.eecs.berkeley.edu/~hui/cs252/rs.htmlWhy Reed-Solomn Codec?● The Reed-Solomn coding is a very efficientand popular Forward Error Correctiontechnique.● It has very much variability in the parametersof implementation, but has regular operations— Great for reconfigurable logic?● Many literatures available.Introduction to RS Codec● Concept of Forward Error Correction» Add redundancy to a message in order to eliminate the need ofretransmission by error correction.● Theory» Reed Solomon coding operates on a finite field called Galios Field.» Generator polynomial: G(x) = (x-a0)(x-a1) · · ·(x-a2t-1), where a is aroot of the binary primitive polynomial x8+x4+x3+x2+1.» Message polynomial: M(x)=(Mk-1xk-1+ Mk-2xk-2 + … + M1x1 + M0 )•x2t-1» Check polynomial: C(x)=M(x) / G(x) = C2t-1x2t-1+ C2t-2x2t-2 + … + C1x1 + C0» Encoded codes: (Mk-1 , Mk-2 , …, M0 , C2t-1 , C2t-2 , …, C0 )Define RS Codec as a Component● Specs and Parameters» m = number of bits per symbol» n = code length in symbols (up to 2m-1)» K = original message length in symbols» r = n-k = number of check symbols» t = 1/2 (n-k) = error correction capability» Total gate counts ≈ 1.6 (182mt + 292t + 215m + 5m2m +208)● InterfaceDecoderdata inputm inputbitsControlinput busm inputbitsDecoder inputmessage start1 input bitDecoderdata outputm outputbitsDecodersystem clk1 input bitDecoder outputmessage start1 output bitEncoderdata inputm inputbitsEncodersystem clk1 input bitEncoder inputmessage start1 input bitEncoderdata outputm outputbitsreset1 input bitEncoder outputmessage start1 output bitArchitecture of RS CodecInputfeedback16 stagescostant multipliersG(15)G(14)G(1)G(0)8ou tp utPowerSumCompu-tationEuclideanAlgorithmChienSearchErrorValueGenera-tionDelayRAMError ValueCorrected DataInputDataDecoder CoreEncoderDecoder• Bit-parallel architecture• 16-stage 8-bit register• 16 GF(28) adders• 16 GF(28) constant multipliers• 4 separate stages• 7 general GF(28) multipliers• 2 GF(28) inverters• 1 delay RAMOutline● Performance Metrics● Implementations● Quantitative Evaluation● Results/Conclusions● Future Work» Power evaluation» Design cost (financial modeling)» Other componentsMetrics● Silicon real estate — Chip area (λ2)● Performance — Throughput (symbol / second)● Combined metric» Throughput / Area (symbol / second•λ2)● Others» Power (mW)» Design cost (engineer month)● Ultimate single metricThroughput / mW / $Custom ASIC Implementation● LSI Logic’s Reed-Solomon CodecLogic Gate CountErrorCorrectionCode Length Technology Die Size ThroughputEncoder DecoderMemory DesignTime8 symbols programmable1 µcompactedarray9.5mm x9.5mm40 MB/s 2K 18K 3Kb RAM4Kb ROM6 monthsRef: Po Tong, “A 40-MHz Encoder-Decoder Chip Generated by a Reed-Solomon Code Compiler”● RS decoder for the Hubble Space TelescopeErrorCorrection (t)Code Length(N)Technology Die Size Throughput Gate CountsStandard cell 82 KFull custom10 symbols programmable 1.6 µ 2-metal8.2 mm x8.4 mm10 MB/s 30 KMicroprocessor Implementation● Algorithm — lookup table based algorithm» The C program was downloaded from the internet.» The program was modified to conform to the specs of the LSILogic chip.» Codes were added to measure the run time of the encodingand decoding functions.● ResultsThroughput (B/s)ErrorCorrection (t)CodeLength (N)Technology Die SizeEncoder DecoderDesignTime8 symbols 255 0.5 µ327 mm2478.4 K 46.2 K 4 daysSUN HyperSparc 100 MHz processorDSP Implementations● Implementation Process» The C code was modified to be compatible with TI C compilerfor TMS320C3X DSPs» Code was compiled with optimization at TI’s online DSP lab» Benchmarked on TI’s EVM module with a 33 MHzTMS320C30 DSP● ResultsTMS320C30: 32-bit floating point, 33 MHz, 16 K words of SRAMThroughputErrorCorrection (t)CodeLength (N)Technology Die SizeEncoder DecoderDesignTime8 symbols 255 0.5 µ51 mm240.6 KB/s18.8 KB/s 1 weekFPGA ImplementationImplementation ProcessAlgorithm / ArchitectureGenerate coefficients with C programVHDL descriptionDesign optimization to reduce gate countsSynthesis with XACT V5.2.1 Xilinx toolsSimulation with ViewsimArea/TimingOptimizationCLB countsCritical path delayFPGA RS Encoder ResultsCLB usage results of Xilinx XC4005 design of RS encoderImplementationsUsage ofI/O (%)Usage of F-generators (%)Usage ofFFs (%)Usage ofCLBs (%)Criticalpath delayProgrammablelength46 77 80 157 / 196 33.8 nsFixed length 31 72 78 153 / 196 29.6 nsPerformance/Area Metric ResultsImplementationsArea = (# ofCLB) x 1.25 M λ2Technology Throughput DesignTimeProgrammablelength196 29.6 MB/sFixed length 191~ 0.8 µ33.7 MB/s4 weeksGF(28) Multiplier Design● Galois Field multiplier is the most criticalcomponent of RS decoder design.● ResultsParts# of CLBs Area = (# of CLB)x 1.25 M λ2Technology Delay Throughput* DesignTimeXC4003 32 40 ~ 0.8 µ49.4 ns 10 MB/sXC4013E(1) 33 41.2 ~ 0.5 µ16.8 ns 30 MB/sXC4013E(2) 30 37.5 ~ 0.5 µ28.2 ns 18 MB/s2 weeks*The critical path delay of decoder is estimated to be twice of that of multiplierXC4013E implementations were referenced from a paper. (1) is with timing optimization, and (2) is with area optimizationComparison0.090.0090.050.0231512812661410.0010.010.1110100100010000uP DSP FPGA CustomEncoderDecoderImplementations Throughput Performace/Area(KB/s / M λ2)Technology Area (mm2)Scaledperformance(to 0.25µm)Microprocessor 478 KB/s 0.09 0.5 µ327 1 MB/sDSP 41 KB/s 0.05~ 0.5 µ 51 82 KB/sFPGA 30 MB/s 151~ 0.8 µ ~ 20 96 MB/sCustom 40 MB/s 12661 µ 90 160 MB/sImplementations Our DesignTimeInitialDesign TimeDesignReuse TimeMicroprocessor 4 days 1 week 4 hrsDSP 1 week 1.5 week 2 daysFPGA 4 weeks 3 months 1 weekCustom 6 months 6 months 6 monthsPower Estimation● Microprocessor» C Instruction level power modeling● DSP» XDS Emulator — a realtime, in-circuit emulator» Assembly Instruction level power modeling● FPGA» Xilinx data sheet» CLB and interconnect power modeling● Custom chip» Buy one and measure
View Full Document
Unlocking...