Lines Matching +full:use +full:- +full:parity
2 NAND Error-correction Code
11 After that the speed was increased by 35-40%.
28 not use the right terminology, my coding theory class was almost 30
32 bytes. This is done by calculating several parity bits over the rows and
33 columns. The parity used is even parity which means that the parity bit = 1
34 if the data over which the parity is calculated is 1 and the parity bit = 0
35 if the data over which the parity is calculated is 0. So the total
36 number of bits over the data over which the parity is calculated + the
37 parity bit is even. (see wikipedia if you can't follow this).
38 Parity is often calculated by means of an exclusive or operation,
59 cp is my abbreviation for column parity, rp for row parity.
61 Let's start to explain column parity.
63 - cp0 is the parity that belongs to all bit0, bit2, bit4, bit6.
69 - cp2 is the parity over bit0, bit1, bit4 and bit5
70 - cp3 is the parity over bit2, bit3, bit6 and bit7.
71 - cp4 is the parity over bit0, bit1, bit2 and bit3.
72 - cp5 is the parity over bit4, bit5, bit6 and bit7.
76 Row parity actually works almost the same.
78 - rp0 is the parity of all even bytes (0, 2, 4, 6, ... 252, 254)
79 - rp1 is the parity of all odd bytes (1, 3, 5, 7, ..., 253, 255)
80 - rp2 is the parity of all bytes 0, 1, 4, 5, 8, 9, ...
82 - rp3 is covers the half rp2 does not cover (bytes 2, 3, 6, 7, 10, 11, ...)
83 - for rp4 the rule is cover 4 bytes, skip 4 bytes, cover 4 bytes, skip 4 etc.
85 so rp4 calculates parity over bytes 0, 1, 2, 3, 8, 9, 10, 11, 16, ...)
86 - and rp5 covers the other half, so bytes 4, 5, 6, 7, 12, 13, 14, 15, 20, ..
90 - rp6 covers 8 bytes then skips 8 etc
91 - rp7 skips 8 bytes then covers 8 etc
92 - rp8 covers 16 bytes then skips 16 etc
93 - rp9 skips 16 bytes then covers 16 etc
94 - rp10 covers 32 bytes then skips 32 etc
95 - rp11 skips 32 bytes then covers 32 etc
96 - rp12 covers 64 bytes then skips 64 etc
97 - rp13 skips 64 bytes then covers 64 etc
98 - rp14 covers 128 bytes then skips 128
99 - rp15 skips 128 bytes then covers 128
101 In the end the parity bits are grouped together in three bytes as
114 nicer picture.(but they use line parity as term where I use row parity)
115 Oh well, I'm graphically challenged, so suffer with me for a moment :-)
123 Implementing the parity calculation is pretty simple.
175 not going to bring me a Nobel prize :-)
180 For the column parity this is easy. We can just xor the bytes and in the
193 const char parity[256] = {
241 (parity[rp7] << 7) |
242 (parity[rp6] << 6) |
243 (parity[rp5] << 5) |
244 (parity[rp4] << 4) |
245 (parity[rp3] << 3) |
246 (parity[rp2] << 2) |
247 (parity[rp1] << 1) |
248 (parity[rp0]);
250 (parity[rp15] << 7) |
251 (parity[rp14] << 6) |
252 (parity[rp13] << 5) |
253 (parity[rp12] << 4) |
254 (parity[rp11] << 3) |
255 (parity[rp10] << 2) |
256 (parity[rp9] << 1) |
257 (parity[rp8]);
259 (parity[par & 0xf0] << 7) |
260 (parity[par & 0x0f] << 6) |
261 (parity[par & 0xcc] << 5) |
262 (parity[par & 0x33] << 4) |
263 (parity[par & 0xaa] << 3) |
264 (parity[par & 0x55] << 2);
274 I also introduced the parity lookup. I expected this to be the fastest
275 way to calculate the parity, but I will investigate alternatives later
289 In step 1 we moved from bit-wise calculation to byte-wise calculation.
290 However in C we can also use the unsigned long data type and virtually
294 Of course this means some modification as the row parity is byte by
296 for the column parity we use the par variable. When extending to 32 bits
321 extern const char parity[256];
351 long; also the column parity calculation needs to be changed.
375 (parity[rp7] << 7) |
376 (parity[rp6] << 6) |
377 (parity[rp5] << 5) |
378 (parity[rp4] << 4) |
379 (parity[rp3] << 3) |
380 (parity[rp2] << 2) |
381 (parity[rp1] << 1) |
382 (parity[rp0]);
384 (parity[rp15] << 7) |
385 (parity[rp14] << 6) |
386 (parity[rp13] << 5) |
387 (parity[rp12] << 4) |
388 (parity[rp11] << 3) |
389 (parity[rp10] << 2) |
390 (parity[rp9] << 1) |
391 (parity[rp8]);
393 (parity[par & 0xf0] << 7) |
394 (parity[par & 0x0f] << 6) |
395 (parity[par & 0xcc] << 5) |
396 (parity[par & 0x33] << 4) |
397 (parity[par & 0xaa] << 3) |
398 (parity[par & 0x55] << 2);
404 The parity array is not shown any more. Note also that for these
421 rp14). That is why some places refer to inverse parity.
538 Measurements showed this was a good move. The run-time roughly halved
543 statements. Why not keep a running parity and only keep the last if
579 As you can see tmppar is used to accumulate the parity within a for
584 contains the running parity for this iteration. So instead of having:
616 Again a use of the commutative property of xor.
657 Not a big change, but every penny counts :-)
683 We can simply calculate the total parity. If this is 0 then rp4 = rp5
684 etc. If the parity is 1, then rp4 = !rp5;
698 kind of other things, like having dedicated parity arrays to avoid the
699 shift after parity[rp7] << 7; No gain.
700 Change the lookup using the parity array by using shift operators (e.g.
701 replace parity[rp7] << 7 with::
710 The only marginal change was inverting the parity bits, so we can remove
740 (gcc 4.2, -O3)
751 5 (big endian mode, gcc 4.1.2, -O3)