Differences

This shows you the differences between two versions of the page.

--- tanszek:oktatas:techcomm:error_detection_and_correction [2025/10/27 19:44] – [Error Detection and Correction Using Hamming Codes] knehez
+++ tanszek:oktatas:techcomm:error_detection_and_correction [2025/10/28 08:30] (current) – [Example 1.] knehez
@@ Line 34: / Line 34: @@
 If two code-words are given, for example : **0101110** and **0111110** and the only difference between them is 1 bit, then the '**Hamming distance**' of these code-words will be 1. This is an interesting measure for distance because it does not matter which bit in the row is different or whether it belongs to a binary or decimal system. So for example : **45635263** and **45615263** have the **Hamming distance** of 1 too. It does not matter that 10 different digits could be in the place of the wrong digit.
-The **Hamming-style** correction code supposed to increase the number of parity bits. To correct single bit errors we have to use **k** number of parity bits using this formula:
+The **Hamming-style** correction code supposed to increase the number of parity bits. To correct single bit errors, we have to use \(r\) number of parity bits using this formula:
-$$ n + 1 \le 2^k $$
+$$ 2^r \ge m + r + 1 $$
 According to this formula the necessary number of parity bits which are needed to correct single bit errors are stated in the following table:
-^ data bits ^ number of parity bits (k) ^ whole bit length (n) ^ % of added bits ^
+^ Data bits (\(m\)) ^ number of parity bits (\(r\)) ^ whole bit length (\(n = m + r\)) ^ % of added bits ^
-| 4 | 3 | 7 | 66 |
+| 4 | 3 | 7 | 75 |
 | 8 | 4 | 12 | 50 |
 | 16 | 5 | 21 | 31 |
@@ Line 94: / Line 94: @@
 |p1|p2|1|p4|0|1|0|
-**p1**: Covers 1, 0, 0 (positions 1, 3, 5, 7), so p1 = 1 (to make the total even).
+**p1**: Covers 1, 0, 1 (positions 1, 3, 5, 7), so p1 = 0 (to make the total even).
-**p2**: Covers 0, 1, 0 (positions 2, 3, 6, 7), so p2 = 1 (to make the total even).
+**p2**: Covers 1, 1, 0 (positions 2, 3, 6, 7), so p2 = 0 (to make the total even).
 **p4**: Covers 0, 1, 0 (positions 4, 5, 6, 7), so p4 = 1 (to make the total even).
 Thus, the final transmitted Hamming code is:
-<code>1 1 1 1 0 1 0</code>
+<code>0 0 1 1 0 1 0</code>
 Let's suppose that because of an error the 3rd bit goes wrong. In this case **p1** and **p2** will be wrong. Because of the **3rd** bit the first and second parity bit will give us wrong values, but the others will not because they do not calculate with the bit standing at the **3rd** place.
@@ Line 111: / Line 111: @@
 ==== Example 2. ====
-Assume that, we try to transmit 16 bits: ''1001011101011011''
+Assume that we try to transmit 16 bits: ''1001011101011011''
 The following table show the placement of the __parity bits__ and the __data bits__:
-| 1| 2|3| 4|5|6|7| 8|9|10|11|12|13|14|15|16|17|18|19|20|21|
+| 1| 2|3| 4|5|6|7| 8|9|10|11|12|13|14|15|16 |17|18|19|20|21|
-|p1|p2|1|p4|0|0|1|p8|0|1|1|1|0|1|0|p16|1|1|0|1|1|
+|p1|p2|1|p4|0|0|1|p8|0|1 |1 |1 |0 |1 |0 |p16|1 |1 |0 |1 |1 |
+p1: Covers (positions: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19), so p1 = (1, 0, 1, 0, 1, 0, 0, 1, 0, 1) -> **1**
+p2: Covers (positions: 2, 3, 6,	7, 10, 11, 14, 15, 18, 19) so p2 = (1, 0, 1, 1, 1, 1, 0, 1, 0) -> **0**
+p4: Covers (positions: 4, 5, 6, 7, 12, 13, 14, 15, 20, 21) so p4 = (0, 0, 1, 1, 0, 1, 0, 1, 1) -> **1**
+p8: Covers (positions: 8, 9, 10, 11, 12, 13, 14, 15) so p8 = (0, 1, 1, 1, 0, 1, 0) -> **0**
+p16: Covers (positions: 16, 17, 18, 19, 20, 21) so p16 = (1, 1, 0, 1, 1) -> **0**
+Encoded message with parity bits will be:
+| 1| 2|3| 4|5|6|7| 8|9|10|11|12|13|14|15|16|17|18|19|20|21|
+| 1| 0|1| 1|0|0|1| 0|0|1 | 1| 1| 0| 1| 0| 0| 1| 1| 0| 1| 1|