Algorithm for a 3-dimensional parity-check code?

This expla开发者_如何学Goins it but only for 2 dimensions : http://en.wikipedia.org/wiki/Multidimensional_parity-check_code

While for a 2-dimensional it's rather easy, how would you code it for 3 or more dimensions ?

Thank you.

---

As the Wikipedia article says, a multi-dimensional parity check of d dimensions corrects d/2 errors. Thus a three-dimensional parity check doesn't have a clear advantage over a two-dimensional parity check. (The article isn't clear what to do with odd dimensions, so it's possible that there's some advantage, but the only article I found is behind a pay-wall, and I don't have time to derive it myself.)

Anyway, here's a graphic example of a four-dimensional parity check for the trivial case of a 1×1×1×1 array, followed by the more interesting cases of arrays sized 2×2×2×2, 3×3×3×3, and 4×4×4×4. I filled in each of the arrays with sequential decimal digits and the corresponding parity values.

1×1×1×1 (5/1 original size; 5× expansion)
1 1 1
1
1

The letters "a" through "h" after this example are footnotes that explain how each of the parity codes are calculated.

2×2×2×2 (24/16 original size; 1.5× expansion)
1  2   3  4   2a  6e
5  6   7  8   4b

9  0   1  2       0f
3  4   5  6

4c 2d

0g     6h

Notes for the 2×2×2×2 array:
a. Sum of 1, 2, 3, 4, 9, 0, 1, 2 (modulo 10) -- horizontal dimension.
b. Sum of 5, 6, 7, 8, 3, 4, 5, 6 (modulo 10).
c. Sum of 1, 5, 9, 3, 3, 7, 1, 5 (modulo 10) -- vertical dimension.
d. Sum of 2, 6, 0, 4, 4, 8, 2, 6 (modulo 10).
e. Sum of 1, 2, 3, 4, 5, 6, 7, 8 (modulo 10) -- a dimension that doesn't fit on a two-dimensional screen; upper two 2×2 blocks.
f. Sum of 9, 0, 1, 2, 3, 4, 5, 6 (modulo 10); lower two 2×2 blocks.
g. Sum of 1, 5, 9, 3, 2, 6, 0, 4 (modulo 10) -- another dimension that doesn't fit on a two-dimensional screen; left two 2×2 blocks.
h. Sum of 3, 7, 1, 5, 4, 8, 2, 6 (modulo 10); right two 2×2 blocks.

3×3×3×3 (93/81 original size; 1.148× expansion)
1 2 3  4 5 6  7 8 9  4  8
0 1 2  3 4 5  6 7 8  7
9 0 1  2 3 4  5 6 7  0

8 9 0  1 2 3  4 5 6     7
7 8 9  0 1 2  3 4 5
6 7 8  9 0 1  2 3 4

5 6 7  8 9 0  1 2 3     6
4 5 6  7 8 9  0 1 2
3 4 5  6 7 8  9 0 1

0 7 4

6      7      8

4×4×4×4 (272/256 original size; 1.0625× expansion)
1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6  8  0
7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2  2
3 4 5 6  7 8 9 0  1 2 3 4  5 6 7 8  6
9 0 1 2  3 4 5 6  7 8 9 0  1 2 3 4  0

5 6 7 8  9 0 1 2  3 4 5 6  7 8 9 0     6
1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6
7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2
3 4 5 6  7 8 9 0  1 2 3 4  5 6 7 8

9 0 1 2  3 4 5 6  7 8 9 0  1 2 3 4     2
5 6 7 8  9 0 1 2  3 4 5 6  7 8 9 0
1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6
7 8 9 0  1 2 3 4  5 6 7 8  9 0 1 2

3 4 5 6  7 8 9 0  1 2 3 4  5 6 7 8     8
9 0 1 2  3 4 5 6  7 8 9 0  1 2 3 4
5 6 7 8  9 0 1 2  3 4 5 6  7 8 9 0
1 2 3 4  5 6 7 8  9 0 1 2  3 4 5 6

8 2 6 0

0        6        2        8

Since the 4×4×4×4 array is only a 6.25% expansion, I don't see much sense in going any farther than that, but the pattern should be evident if you want to do so.

(I know I'm late to the party. But I hope this is useful in case someone else asks the same question.)

---

The 2D example from wikipedia distributes the digits into several rows and calculates the parity for each row and column.

A 3D version would distribute the digits into rows, columns and layers (think of multiple grids stacked on one another, forming a cube). Then you just need to calculate the parity bits for the layer component and you are done.