2

I have to do the scheme of the non-systematic Hamming code encoder (not cyclic but classic). But I have not found any source where it would be written how to build a generating matrix and create a system of linear equations for finding symbols of code combinations. How is this done?

Once again, I consider the non-systematic classical (n, k) Hamming code. For example, (7, 4) Hamming code.

Thank you in advance for your detailed answers.

alexhak
  • 143
  • 7
  • (7,4) Hamming is really easy to understand. I'm not sure how it could be a struggle. But are you asking for something far more general? – jonk Jun 19 '19 at 01:46
  • He's looking for the XOR parity codecs – Tony Stewart EE75 Jun 19 '19 at 01:48
  • Just to get the link into here: Hamming. – jonk Jun 19 '19 at 04:22
  • @jonk Systematic Hamming code is really easy to understand. But the unsystematic is not clear. For example, there is a matrix G of an unsystematic (7, 4) Hamming code. How to create a system of linear equations for finding symbols of code combinations? $$G = \begin{pmatrix}1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1\end{pmatrix}$$ – alexhak Jun 19 '19 at 10:46

1 Answers1

1

AS I recall from the '70's it uses XOR gates but now in a small CPLD.
P1=d0 ⊕ d2 ⊕ d4 ⊕ d6
P2=d1 ⊕ d2 ⊕ d4 ⊕ d6
P3=d3 ⊕ d4 ⊕ d5⊕ d6

b3, b2, b1, P3, b0, P2, P1 7 bit string = 3 parity bits + 4 data bits = Hamming 7,4
sent as d6 d5 d4 d3 d2 d1 d0 repeat for both 4b nibble to get 14 bit string.

Dave? @Jonk correct me if I missed something.

Tony Stewart EE75
  • 1
  • 3
  • 54
  • 185
  • You are right, but you described a systematic (7, 4)-code. Non-systematic should work differently, because the test matrix is chaotic. – alexhak Jun 19 '19 at 10:33
  • Not so chaotic, just funky: swap 2 columns, then XOR 2 or 3 rows and replace any row with result. But repeat same for G matrix decoder. – Tony Stewart EE75 Jun 19 '19 at 11:43
  • As I understand it, is not necessary to rearrange only 2 columns (can be any number). For example, $$G = \begin{pmatrix}1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1\end{pmatrix}$$ – alexhak Jun 19 '19 at 11:51
  • But then it turns out that the test matrix will look like this: $$H = \begin{pmatrix}0 & 1 & 0 & 1 & * & * & * \\ 0 & 0 & 1 & 0 & * & * & * \\ 0 & 0 & 0 & 1 & * & * & \end{pmatrix}$$ How do I determine the remaining " * *"columns? – alexhak Jun 19 '19 at 11:54
  • Looks that way! As long as identical sequential operations are done, 1⊕1=0 – Tony Stewart EE75 Jun 19 '19 at 11:55
  • \begin{matrix} {H= \begin{bmatrix} 0&0&0&1&1&1&1\ 0&1&1&0&0&1&1\ 1&0&1&0&1&0&1 \end{bmatrix}} \ {C_{7} \leftrightarrow C_{1}}\ {H_{1}= \begin{bmatrix} 1&0&0&1&1&1&0\ 1&1&1&0&0&1&0\ 1&0&1&0&1&0&1 \end{bmatrix}}\ {C_{2} \leftrightarrow C_{6}}\ {H_{2}= \begin{bmatrix} 1&1&0&1&1&0&0\ 1&1&1&0&0&1&0\ 1&0&1&0&1&0&1 \end{bmatrix}}\ {C_{4} \leftrightarrow C_{5}}\ {H_{3}= \begin{bmatrix} 1&1&0&1&1&0&0\ 1&1&1&0&0&1&0\ 1&0&1&1&0&0&1 \end{bmatrix}}\ \end{matrix} – Tony Stewart EE75 Jun 19 '19 at 12:04
  • \begin{matrix} {H_{4}=\left[ \begin{array}{cccccc|c} 1&1&0&1&1&0&0\ 1&1&1&0&0&1&0\ 1&0&1&1&0&0&1\end{array} \right]}\ {;;;;;;;;;;;;;;;;;;;;A;;;;;;;;;I_{3}} \end{matrix} – Tony Stewart EE75 Jun 19 '19 at 12:05
  • $$GH^{T}=0$$ Now if you understand this write your own answer – Tony Stewart EE75 Jun 19 '19 at 12:10
  • \begin{matrix} {G_{3}=\left[ \begin{array}{cccc|ccc} 1&0&0&0&1&1&1\ 0&1&0&0&1&1&0\ 0&0&1&0&0&1&1\ 0&0&0&1&1&0&1\end{array} \right]}\ {;;;;;;;;;;I_{4};;;;;;;;; A^{T}} \end{matrix} – Tony Stewart EE75 Jun 19 '19 at 12:16
  • \begin{matrix} {C_{4} \leftrightarrow C_{5}}\ {G_{2}=\left[ \begin{array}{cccc|ccc} 1&0&0&1&0&1&1\ 0&1&0&1&0&1&0\ 0&0&1&0&0&1&1\ 0&0&0&1&1&0&1\end{array} \right]}\ {C_{2} \leftrightarrow C_{6}}\ {G_{1}=\left[ \begin{array}{cccc|ccc} 1&1&0&1&0&0&1\ 0&1&0&1&0&1&0\ 0&1&1&0&0&0&1\ 0&0&0&1&1&0&1\end{array} \right]}\ {C_{7} \leftrightarrow C_{1}}\ {G=\left[ \begin{array}{cccc|ccc} 1&1&0&1&0&0&1\ 0&1&0&1&0&1&0\ 1&1&1&0&0&0&0\ 1&0&0&1&1&0&0\end{array} \right]}\end{matrix} – Tony Stewart EE75 Jun 19 '19 at 12:16
  • G times H transposed $GH^T=0$ – Tony Stewart EE75 Jun 19 '19 at 12:17
  • $$GH^T=0$$ Thus, if $$G = \begin{pmatrix}1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1\end{pmatrix}$$ that $$H = \begin{pmatrix}1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1\end{pmatrix}$$ – alexhak Jun 19 '19 at 12:43
  • Can U paste into Answer – Tony Stewart EE75 Jun 19 '19 at 12:43
  • And this test matrix H can be considered as non-systematic? Since it is obtained from the non-systematic matrix G. – alexhak Jun 19 '19 at 12:47
  • Yes That’s what it seems, since you create your own sequence and reverse it like CRC – Tony Stewart EE75 Jun 19 '19 at 12:48