k383556 / bch_verilog Goto Github PK
View Code? Open in Web Editor NEWThis project forked from russdill/bch_verilog
Verilog based BCH encoder/decoder
License: Other
This project forked from russdill/bch_verilog
Verilog based BCH encoder/decoder
License: Other
Verilog BCH encoder/decoder. This is a Verilog based BCH encoder and decoder for single bit, dual bit, and 3 or more bit error correction. The equations and layout for the encoder and decoders is taken from "The design of a vhdl based synthesis tool for bch codecs." by Ernest Jamro. The decoder/encoder is completely parameterizable. The two main parameter are: DATA_BITS - The number of data bits T - The number of bits that can be corrected The module bch_param generates a BCH parameter set: `include "bch_params.vh" localparam [`BCH_PARAM_SZ-1:0] P = bch_params(DATA_BITS, T); The generated parameters are passed to the BCH modules and can be access with the following: `BCH_M(P) - Degree of the field `BCH_N(P) - Actual code size (padded) `BCH_K(P) - Actual data size (padded) `BCH_T(P) - Actual bits corrected (may be more than specified) `BCH_DATA_BITS(P) - Data bits `BCH_ECC_BITS(P) - Generate ECC bits `BCH_CODE_BITS(P) - Data bits + ECC bits `BCH_SYNDROMES_SZ(P) - Bits required for syndromes passed between modules `BCH_SIGMA_SZ(P) - Bits required for sigma equation passed between modules `BCH_ERR_SZ(P) - Bits required for number of errors `BCH_PARAM_SZ - Bits required to hold parameters Note that the number of errors correctable for a given polynomial is sparse. The search function will choose the next highest number of correctable errors rather than trying to move to the next polynomial. For instance, if DATA_BITS=64, T=8 is seleceted, (127, 71, 9) is chosen rather than (255, 191, 8). Many modules accept a PIPELINE_STAGES and/or a REG_RATIO parameter. These parameters relate to area/speed/latency optimizations. There is not a hard and fast rule of which setting will give the best speed or area result. PIPELINE_STAGES adds additional pipelining stages to operation, increasing register count and latency, but possibly increasing speed. For modules that accept input in parallel and have duplicated register sets for dealing with the parallel input, REG_RATIO reduces the number of registers used. REG_RATIO=1 will include all registers, REG_RATIO=2 will calculate every other register asyncronously from the previous register, REG_RATIO=3 will calculate every third register asyncrounously and so on. The maximum allowable REG_RATIO is REG_RATIO=BITS (the input width). Note that when compiling with Xilinx tools, the '-loop_iteration_limit' option to XST is required to be set above the `BCH_N constant. Choosing a value that is DATA_BITS is usually safe. The code currently compiles under Icarus Verilog, Xilinx Isim and Xilinx XST. Bit Order: When operating with multi-bit input/output, the first bit in each sequence is the high bit of the first word. If padding is added to the last word is a sequence, it is added to the lowest bits of the word. Modules: The encoder consists of a single module, but the decoder consists of several modules that are meant to be used together. Depending on requirements, certain modules can be shared between decoders. Slice counts and max frequencies are show below each module based on the Xilinx Virtex-6 LX240T-3, built with all default options except for '-opt_level 2' passed to XST. Additional optimizations may yield lower area/higher speeds. bch_encode - Performs encoding of input data via a large LFSR. Takes a BITS wide input. For the first ceil(`BCH_DATA_BITS / BITS) cycles (including cycle 0) the output mirrors the input. Then, for ceil(`BCH_ECC_BITS / BITS) cycles the output contains the ECC bits. In the case that `BCH_DATA_BITS % BITS is non-zero, the low bits of the last data word will be ignored. A pipeline stage can be added by setting the PIPELINE_STAGES=1 parameter. T=1,DATA_BITS=64: BITS= 1,PIPELINE_STAGES=0 12 slices 503 MHz BITS= 8,PIPELINE_STAGES=1 18 slices 543 MHz BITS=16,PIPELINE_STAGES=0 18 slices 543 MHz T=1,DATA_BITS=256: BITS=16,PIPELINE_STAGES=0 22 slices 543 MHz T=3,DATA_BITS=256: BITS=16,PIPELINE_STAGES=0 72 slices 390 MHz T=8,DATA_BITS=256: BITS=16,PIPELINE_STAGES=1 125 slices 447 MHz T=12,DATA_BITS=256: BITS=16,PIPELINE_STAGES=1 183 slices 387 MHz T=12,DATA_BITS=4096: BITS= 8,PIPELINE_STAGES=0 150 slices 375 MHz BITS=16,PIPELINE_STAGES=0 295 slices 318 MHz bch_blank_ecc - Allows the ECC on erased flash to be valid. It does this by precomputing the ECC of an all 1's input and then inverting it. This module provides this data so it can be XOR'd with the ECC bit output from the encode module and XOR'd again before input to the bch_syndrome module. bch_syndrome - Calculates the syndrome equations. Takes a BITS wide input. Operates for ceil(`BCH_CODE_BITS / BITS) cycles to produce the compact syndrome equations. Note that bch_syndrome expects the data and ecc input to be merged together without pad bits in the case of `BCH_DATA_BITS % BITS being non-zero, which is not what bch_encode produces. It is recommended to make BITS divisible by `BCH_DATA_BITS. In the event that `BCH_CODE_BITS % BITS is non-zero, the upper bits of the final word are ignored. Up to two pipeline stages can be added by setting the PIPELINE_STAGES parameter. T=1,DATA_BITS=64: BITS= 1,PIPELINE_STAGES=0,REG_RATIO=1 8 slices 464 MHz BITS= 4,PIPELINE_STAGES=1,REG_RATIO=4 13 slices 506 MHz BITS= 8,PIPELINE_STAGES=2,REG_RATIO=1 30 slices 485 MHz BITS=16,PIPELINE_STAGES=2,REG_RATIO=4 48 slices 408 MHz T=1,DATA_BITS=256: BITS=16,PIPELINE_STAGES=2,REG_RATIO=4 52 slices 386 MHz T=3,DATA_BITS=256: BITS=16,PIPELINE_STAGES=2,REG_RATIO=8 66 slices 451 MHz T=8,DATA_BITS=256: BITS=16,PIPELINE_STAGES=1,REG_RATIO=16 43 slices 508 MHz T=12,DATA_BITS=256: BITS= 4,PIPELINE_STAGES=2,REG_RATIO=4 21 slices 488 MHz BITS= 8,PIPELINE_STAGES=2,REG_RATIO=8 22 slices 512 MHz BITS=16,PIPELINE_STAGES=2,REG_RATIO=16 42 slices 485 MHz T=12,DATA_BITS=4096: BITS= 8,PIPELINE_STAGES=1,REG_RATIO=8 25 slices 512 MHz BITS=16,PIPELINE_STAGES=1,REG_RATIO=16 42 slices 453 MHz bch_errors_present - Determines based on syndromes if any errors are present (Not required for decoding). This module can be used to allow several bch_syndrome modules to share bch_sigma_* and bch_error_* modules or to determine that the error is data free before allowing bch_sigma_* to complete. Up to two pipeline stages can be added by setting the PIPELINE_STAGES parameter. bch_sigma_* - Key equation solvers (sigma). Takes syndrome equations as input and produces the key equation, as well as the number of bit errors detected. Solving the key equation is required for T > 2 and optional for T == 2, and not supported for T == 1. bch_sigma_bma_serial - Serial Berlekamp–Massey algorithm with inversion. This option takes longer but requires less space than the parallel option. This option takes `BCH_T(P) * (`BCH_M(P) + 2) - 2 cycles to solve the key equation. Because of variability in the basis conversion circuits, the performance can vary widely for different values of `BCH_M. T= 2,DATA_BITS=64 63 slices 376 MHz T= 2,DATA_BITS=256 80 slices 345 MHz T= 2,DATA_BITS=1024 95 slices 263 MHz T= 2,DATA_BITS=4096 120 slices 276 MHz T= 8,DATA_BITS=256 192 slices 217 MHz T= 8,DATA_BITS=1024 225 slices 262 MHz T= 8,DATA_BITS=4096 272 slices 190 MHz T=12,DATA_BITS=256 266 slices 208 MHz T=12,DATA_BITS=1024 299 slices 205 MHz T=12,DATA_BITS=4096 429 slices 194 MHz bch_sigma_bma_parallel - Parallel Berlekamp–Massey algorithm without inversion. This option operates in less cycles than the serial option, but requires more gates. This option takes `BCH_T(P) * 2 - 1 cycles to solve the key equation. T= 2,DATA_BITS=64 92 slices 330 MHz T= 2,DATA_BITS=256 138 slices 327 MHz T= 2,DATA_BITS=1024 222 slices 284 MHz T= 2,DATA_BITS=4096 335 slices 236 MHz T= 8,DATA_BITS=256 444 slices 223 MHz T= 8,DATA_BITS=1024 586 slices 251 MHz T= 8,DATA_BITS=4096 754 slices 212 MHz T=12,DATA_BITS=256 576 slices 230 MHz T=12,DATA_BITS=1024 761 slices 229 MHz T=12,DATA_BITS=4096 1025 slices 191 MHz bch_sigma_bma_noinv - Serial Berlekamp–Massey algorithm without inversion. This option takes `BCH_T(P) * (`BCH_M(P) * 2 + 1) cycles to solve the key equation. T= 3,DATA_BITS=256 19 slices 421 MHz T= 3,DATA_BITS=1024 107 slices 348 MHz T= 3,DATA_BITS=4096 128 slices 320 MHz T= 8,DATA_BITS=256 19 slices 307 MHz T= 8,DATA_BITS=1024 231 slices 261 MHz T= 8,DATA_BITS=4096 305 slices 232 MHz T=12,DATA_BITS=256 23 slices 489 MHz T=12,DATA_BITS=1024 342 slices 196 MHz T=12,DATA_BITS=4096 445 slices 203 MHz bch_error_* - Error locator. After 2 cycles, it clocks out a BITS wide error bits word ceil(`BCH_DATA_BITS / BITS) cycles, each cycle representing a set of error locations. If `BCH_DATA_BITS % BITS is non-zero, the low bits of the last word in the output are masked. bch_error_dec - Error location function for T < 3. Takes syndromes directly as input rather than a solved key equation. Same output as bch_error_* above, but also produces the error_count. Up to two pipeline stages for T==2 or one for T==1 can be added by setting the PIPELINE_STAGES parameter. T=1,DATA_BITS=64: BITS= 1,PIPELINE_STAGES=1,REG_RATIO=1 17 slices 491 MHz BITS= 8,PIPELINE_STAGES=1,REG_RATIO=1 45 slices 510 MHz BITS= 8,PIPELINE_STAGES=1,REG_RATIO=8 23 slices 490 MHz BITS=16,PIPELINE_STAGES=0,REG_RATIO=8 32 slices 482 MHz T=1,DATA_BITS=256: BITS=16,PIPELINE_STAGES=0,REG_RATIO=16 31 slices 466 MHz T=1,DATA_BITS=4096: BITS=16,PIPELINE_STAGES=0,REG_RATIO=4 88 slices 423 MHz BITS=16,PIPELINE_STAGES=1,REG_RATIO=16 64 slices 385 MHz T=2,DATA_BITS=64: BITS= 1,PIPELINE_STAGES=2,REG_RATIO=1 36 slices 442 MHz BITS= 8,PIPELINE_STAGES=2,REG_RATIO=8 105 slices 504 MHz BITS= 8,PIPELINE_STAGES=2,REG_RATIO=4 84 slices 488 MHz BITS=16,PIPELINE_STAGES=2,REG_RATIO=1 183 slices 424 MHz T=2,DATA_BITS=256: BITS=16,PIPELINE_STAGES=2,REG_RATIO=8 367 slices 291 MHz T=2,DATA_BITS=4096: BITS=16,PIPELINE_STAGES=1,REG_RATIO=4 821 slices 230 MHz BITS=16,PIPELINE_STAGES=2,REG_RATIO=16 637 slices 215 MHz bch_error_tmec - Error location function for T > 1. Requires the solved key equation as input. Same output as bch_error_* above. Up to two pipeline stages can be added by setting the PIPELINE_STAGES parameter. T=3,DATA_BITS=64: BITS= 1,PIPELINE_STAGES=0,REG_RATIO=1 26 slices 485 MHz BITS= 8,PIPELINE_STAGES=2,REG_RATIO=4 75 slices 457 MHz BITS=16,PIPELINE_STAGES=2,REG_RATIO=8 111 slices 393 MHz T=3,DATA_BITS=256: BITS=16,PIPELINE_STAGES=2,REG_RATIO=4 152 slices 416 MHz T=3,DATA_BITS=4096: BITS=16,PIPELINE_STAGES=2,REG_RATIO=8 314 slices 352 MHz T=8,DATA_BITS=256: BITS=16,PIPELINE_STAGES=2,REG_RATIO=8 373 slices 337 MHz T=8,DATA_BITS=4096: BITS=16,PIPELINE_STAGES=2,REG_RATIO=16 737 slices 251 MHz T=12,DATA_BITS=256: BITS=16,PIPELINE_STAGES=2,REG_RATIO=16 595 slices 297 MHz T=12,DATA_BITS=4096: BITS= 8,PIPELINE_STAGES=2,REG_RATIO=8 585 slices 262 MHz BITS=16,PIPELINE_STAGES=2,REG_RATIO=16 1247 slices 183 MHz sim - Test bench core and example code for connecting together the different modules. Takes an additional parameter to specify the type of key equation solver: OPTION - The type of key equation solver: OPTION == NONE - For T < 3, skip the key solving process OPTION == PARALLEL - For T > 1, use bch_sigma_bma_parallel OPTION == SERIAL - For T > 1, use bch_sigma_bma_serial OPTION == NOINV - For T > 1, use bch_sigma_bma_noinv BITS - The word width for bch_encode, bch_syndrome, and bch_error_*. REG_RATIO - When using multi-bit datastreams, bch_syndrome and bch_error_* create a duplicated register set for each bit. This causes them to instead only create a register for every REG_RATIOth bit. The additional values are calculated asyncronously which may create timing issues, but will reduce register usage. TODO: Improve simulation times. Shared syndrome/chien stages between data streams? Forney algorithm for error location? BTZ algorithm for error location? Encoder Example Output: Note: This includes XOR'ing the ECC data with bch_blank_ecc. The output matches the ECC generated by Linux software BCH. DATA_BITS=4096, T=3, BITS=8, GP(2^13) 0x000: 24 ac a8 48 81 7a 91 03 90 6b 21 21 c6 6a 0f 8d 0x010: b0 de 9d 60 b1 99 fb 62 a6 21 43 4d 48 4a ec 91 0x020: 80 c7 cf 00 b0 b3 eb 60 6e 8f c4 dc bc b3 b1 78 0x030: b7 ea 2b 6e 31 ef b4 62 9f 97 bf 3e 63 24 ec c7 0x040: a3 21 ef 47 55 4b c8 ab a7 ef f5 4e ee 4e 4b dd 0x050: 48 6b 4c 91 f1 db 37 e2 4f 96 0c 9e 73 69 6e e7 0x060: 17 5e 00 2f a3 72 53 47 3a 92 1a 74 bd 14 71 7b 0x070: b4 1a d5 69 a6 64 e5 4d c6 46 f7 8d 50 e1 ce a0 0x080: 01 44 dc 03 04 84 26 08 55 a2 1e aa b9 33 33 73 0x090: 69 7c 04 d3 c8 1d c1 91 b0 1c 3d 61 ca 6b e5 95 0x0a0: d6 bb f9 ac ab 54 65 57 40 52 e8 81 75 7c 6a eb 0x0b0: b8 97 ff 70 f3 4e a3 e7 c4 92 21 88 50 a6 90 a0 0x0c0: 53 50 ce a7 3c 32 8c 79 4f bd 16 9e 51 86 74 a2 0x0d0: 82 cd 23 04 1b 2c d2 37 1e cf 04 3c 91 48 51 23 0x0e0: d7 b0 a3 ae 6d a6 40 da 63 9f d2 c6 75 c8 a8 ea 0x0f0: 3d 40 ae 7b 54 bb f0 a8 d0 59 eb a1 8e 7d e9 1d 0x100: a1 82 4f 42 f2 aa 4f e4 dc 06 33 b9 5c cc 60 b8 0x110: 7e 4c c4 fd a8 d2 55 50 8f d9 9b 1e 9b d2 39 36 0x120: 46 e0 c4 8c 32 df ac 64 f9 aa 85 f2 f1 85 9d e2 0x130: 1f 95 b6 3e ed 06 b3 db f9 6a 23 f3 3a 29 be 75 0x140: da 03 d3 b5 91 ec 7b 22 92 4c 75 25 0b 7c c4 17 0x150: eb 03 7f d7 8a 3f e3 15 69 f4 84 d2 30 fe b8 60 0x160: 43 73 34 87 13 b7 ea 26 ee 5a 41 dd bc b7 4f 78 0x170: 48 db 30 90 7e 00 a0 fd b6 81 a7 6c 9c e7 9b 38 0x180: f8 f1 4b f0 cb 6f d7 97 a1 f4 9b 42 1e 11 28 3d 0x190: da 9a 5b b4 92 d2 d1 24 fc 75 4f f9 54 f5 30 a8 0x1a0: 1a c6 a8 34 61 1c fc c3 71 30 58 e3 39 4f f4 73 0x1b0: 5f 99 ac be 64 3d be c9 ce e8 69 9c c5 2d d1 8b 0x1c0: f4 15 99 e9 cd 49 4b 9b fa 6a 1b f5 22 b0 94 44 0x1d0: ef bf 1f de d3 6c d9 a7 67 58 90 cf 5a db 14 b4 0x1e0: 94 83 f3 28 b7 47 41 6f 5b 36 ca b7 a6 6d f9 4d 0x1f0: ad 47 51 5b fb 29 7d f7 9e 98 8f 3c 22 ff 8c 44 ECC: 24 a2 6b 4d 5b -- Russ Dill <[email protected]>
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.