Exercise DET-05.02 – A flipped bit on the way to your headphones (Solution)

Prof. Dr. Thorsten Jungmann (last updated 2026-11-02)

Relates to DET-05 Codes, code converters and standard components

Task

Your smartphone sends data to wireless headphones via Bluetooth, and electromagnetic interference can flip single bits on the way. Bluetooth protects certain packets with a shortened Hamming code. Here, you work with the form with seven bits from the lesson. The data bits $A$ , $B$ , $C$ and $D$ carry a decimal digit in the binary-coded decimal (BCD) code, $A$ with the weight 8, and three parity bits are added:

Position	1	2	3	4	5	6	7
Bit	$Y_{1}$	$Y_{2}$	$A$	$Y_{4}$	$B$	$C$	$D$

With even parity, $Y_{1}$ completes the positions 3, 5 and 7, $Y_{2}$ the positions 3, 6 and 7, and $Y_{4}$ the positions 5, 6 and 7 to an even number of ones.

a) First without the Hamming code: the digit 4 is sent in the BCD code, followed by one parity bit with even parity. Give the five bits.

b) The bit with the weight 1 of a) flips on the way. Does the receiver notice? In another transmission, the bits with the weights 4 and 2 flip instead. Does the receiver notice this, and which digit does it read?

c) Determine the Hamming distance between the digits 4 and 6, first in the BCD code, then in the BCD code with one parity bit.

d) Determine the code words with seven bits for the digits 4 and 6. What is the Hamming distance between them?

e) The receiver gets 1001000. Which bit has flipped, and which digit was sent? Which digit would the data bits have delivered without the correction?

f) The receiver gets 1000100. Which bit has flipped? Does this change the digit?

g) The digit 4 was sent, and the bits at the positions 3 and 5 have flipped: the receiver gets 1011000. Which bit does the receiver invert, and what does it deliver?

h) Let $Z_{1}$ to $Z_{7}$ be the received bits. Give the expressions of the three results $R_{1}$ , $R_{2}$ and $R_{4}$ of the receiver. Then design the correction of the bit at position 3 with an output of a 3-to-8 decoder and an XOR gate.

◀️ Back to the task

Solution

Given

Given explicitly:

the positions of the parity bits $Y_{1}$ , $Y_{2}$ , $Y_{4}$ and of the data bits $A$ , $B$ , $C$ , $D$ , with even parity
a) and b) the digit 4 with one parity bit, and the bits that flip
c) and d) the digits 4 and 6
e), f) and g) the received code words

Known:

Binary-coded decimal (BCD) code (DET-05)
Parity bit with even parity and Hamming distance (DET-05)
Hamming code with seven bits: positions, sets, finding the flipped bit (DET-05)
The XOR operation delivers a 1 for an odd number of ones (DET-03)
Parity bits and receiver as a circuit, decoder and correction (DET-05, DET-05)

Required

a) the five bits
b) whether the receiver notices each error, and the digit that it reads in the second case
c) the two Hamming distances
d) the two code words and their Hamming distance
e) the flipped bit, the digit sent and the digit without the correction
f) the flipped bit and whether the digit changes
g) the bit that the receiver inverts, and what it delivers
h) the expressions of the results and the correction of position 3

a) One parity bit

The digit 4 is 0100 in the BCD code (DET-05, 1.3). It has one 1, an odd number, so the parity bit with even parity is 1 (DET-05, 2.1). The five bits are 0100 1.

b) One and two flipped bits

If the bit with the weight 1 flips, the receiver gets 0101 1. It counts three ones, an odd number, so it notices the error, but it cannot tell which bit has flipped.

If the bits with the weights 4 and 2 flip, it gets 0010 1. It counts two ones, an even number, and notices nothing. It reads 0010, the digit 2. Two flipped bits go unnoticed (DET-05, 2.1).

c) Hamming distance

The Hamming distance is the number of positions in which two code words differ (DET-05, 2.1). In the BCD code, 0100 and 0110 differ only in the bit with the weight 2: distance 1. So one flipped bit turns one valid digit into the other, and nothing reveals it.

With the parity bit, the code words are 0100 1 and 0110 0. They differ in the bit with the weight 2 and in the parity bit: distance 2. One flipped bit no longer leads from one valid code word to another.

d) Code words with seven bits

Each parity bit is 1 if its three data bits contain an odd number of ones (DET-05, 4.3). For the digit 4, with $A = 0$ , $B = 1$ , $C = 0$ and $D = 0$ :

Y_{1} Y_{2} Y_{4} = A \oplus B \oplus D = 0 \oplus 1 \oplus 0 = 1 = A \oplus C \oplus D = 0 \oplus 0 \oplus 0 = 0 = B \oplus C \oplus D = 1 \oplus 0 \oplus 0 = 1

Position	1	2	3	4	5	6	7
Bit	$Y_{1}$	$Y_{2}$	$A$	$Y_{4}$	$B$	$C$	$D$
Digit 4	1	0	0	1	1	0	0

For the digit 6, with $A = 0$ , $B = 1$ , $C = 1$ and $D = 0$ :

Y_{1} Y_{2} Y_{4} = A \oplus B \oplus D = 0 \oplus 1 \oplus 0 = 1 = A \oplus C \oplus D = 0 \oplus 1 \oplus 0 = 1 = B \oplus C \oplus D = 1 \oplus 1 \oplus 0 = 0

Position	1	2	3	4	5	6	7
Bit	$Y_{1}$	$Y_{2}$	$A$	$Y_{4}$	$B$	$C$	$D$
Digit 6	1	1	0	0	1	1	0

So the code words are 1001100 and 1100110. They differ at the positions 2, 4 and 6: distance 3.

Check by counting the ones of each set in 1100110: positions 1, 3, 5 and 7 hold 1, 0, 1 and 0, positions 2, 3, 6 and 7 hold 1, 0, 1 and 0, positions 4, 5, 6 and 7 hold 0, 1, 1 and 0; each set has an even number of ones ✓

The distances 1, 2 and 3 are those of the table in the lesson (DET-05, 2.1): with 3, a code can correct one flipped bit or detect two.

e) Finding the flipped bit

The receiver forms the XOR over each set of four positions, the parity bit included (DET-05, 4.3). For $Z_{1} = 1$ , $Z_{2} = 0$ , $Z_{3} = 0$ , $Z_{4} = 1$ , $Z_{5} = 0$ , $Z_{6} = 0$ and $Z_{7} = 0$ :

R_{1} R_{2} R_{4} = Z_{1} \oplus Z_{3} \oplus Z_{5} \oplus Z_{7} = 1 \oplus 0 \oplus 0 \oplus 0 = 1 = Z_{2} \oplus Z_{3} \oplus Z_{6} \oplus Z_{7} = 0 \oplus 0 \oplus 0 \oplus 0 = 0 = Z_{4} \oplus Z_{5} \oplus Z_{6} \oplus Z_{7} = 1 \oplus 0 \oplus 0 \oplus 0 = 1

Read with the weights 1, 2 and 4, the results give $1 + 4 = 5$ : the bit at position 5 has flipped. The receiver inverts it and gets 1001100. The data bits at the positions 3, 5, 6 and 7 are 0100, the digit 4.

Without the correction, the data bits of 1001000 are 0000, the digit 0, a valid digit that the data bits alone would not reveal as wrong.

f) A flipped parity bit

For $Z_{1} = 1$ , $Z_{2} = 0$ , $Z_{3} = 0$ , $Z_{4} = 0$ , $Z_{5} = 1$ , $Z_{6} = 0$ and $Z_{7} = 0$ :

R_{1} R_{2} R_{4} = Z_{1} \oplus Z_{3} \oplus Z_{5} \oplus Z_{7} = 1 \oplus 0 \oplus 1 \oplus 0 = 0 = Z_{2} \oplus Z_{3} \oplus Z_{6} \oplus Z_{7} = 0 \oplus 0 \oplus 0 \oplus 0 = 0 = Z_{4} \oplus Z_{5} \oplus Z_{6} \oplus Z_{7} = 0 \oplus 1 \oplus 0 \oplus 0 = 1

The results give 4: the bit at position 4 has flipped, a parity bit. The data bits at the positions 3, 5, 6 and 7 are still 0100, so the digit 4 stays correct. The receiver finds the error all the same.

g) Two flipped bits

For $Z_{1} = 1$ , $Z_{2} = 0$ , $Z_{3} = 1$ , $Z_{4} = 1$ , $Z_{5} = 0$ , $Z_{6} = 0$ and $Z_{7} = 0$ :

R_{1} R_{2} R_{4} = Z_{1} \oplus Z_{3} \oplus Z_{5} \oplus Z_{7} = 1 \oplus 1 \oplus 0 \oplus 0 = 0 = Z_{2} \oplus Z_{3} \oplus Z_{6} \oplus Z_{7} = 0 \oplus 1 \oplus 0 \oplus 0 = 1 = Z_{4} \oplus Z_{5} \oplus Z_{6} \oplus Z_{7} = 1 \oplus 0 \oplus 0 \oplus 0 = 1

The results give $2 + 4 = 6$ . The receiver takes this for the position of a single flipped bit and inverts bit 6, which was correct. It delivers 1011010, with the data bits 1010. This is not a valid digit in the BCD code. Now the bits at the positions 3, 5 and 6 are wrong.

So this code corrects one flipped bit or detects two, but it cannot do both at once (DET-05, 2.2). A receiver that only detects errors would see that the results are not all 0, and it would reject the code word.

h) Receiver and correction

Each result is the XOR over its set of four positions (DET-05, 4.3):

R_{1} R_{2} R_{4} = Z_{1} \oplus Z_{3} \oplus Z_{5} \oplus Z_{7} = Z_{2} \oplus Z_{3} \oplus Z_{6} \oplus Z_{7} = Z_{4} \oplus Z_{5} \oplus Z_{6} \oplus Z_{7}

At the inputs of a 3-to-8 decoder with the weights 1, 2 and 4, the three results set exactly the output with the number of the flipped bit (DET-05, 3.2). Each output is a minterm of the results (DET-05, 3.1). For position 3, the code word is 011 for the weights 4, 2 and 1:

X_{3} = \overline{R_{4}} \cdot R_{2} \cdot R_{1}

An XOR gate combines the received bit with this output: it passes the bit if $X_{3} = 0$ and inverts it if $X_{3} = 1$ (DET-05, 4.3):

A_{c} = Z_{3} \oplus X_{3}

Check for the case of e), with $R_{1} = 1$ , $R_{2} = 0$ , $R_{4} = 1$ and $Z_{3} = 0$ :

X_{3} = \overline{1} \cdot 0 \cdot 1 = 0

So $A_{c} = 0 \oplus 0 = 0$ : bit 3 stays as it is ✓

In the simulation, the parity generator forms the parity bits, each electric line can be flipped, and the receiver and the decoder find the flipped bit. The simulation starts with the digit 4 and a flip at position 5, the case of e). Switch the flip inputs: with one flip, the corrected data bits always show the digit that was sent. With the flips at 3 and 5, the case of g), they do not.

Simulation of the Hamming code with seven bits: parity generator, flip inputs, receiver, a demultiplexer as a 3-to-8 decoder and the correction of the data bits; with the digit four and the bit at position 5 flipped, the results show five, and the corrected data bits are the digit four again

Open in the simulator

Circuit as text (File → Import From Text…)

<cir f="1" ts="0.000005" ic="1.500424758475255" cb="50" pb="50" vr="5" mts="5e-11">
  <L x="96 64 96 16" f="2"/>
  <L x="144 64 144 16" f="2" p="1"/>
  <L x="192 64 192 16" f="2"/>
  <L x="240 64 240 16" f="2"/>
  <Xor x="304 112 400 112" f="0" o="5"/>
  <Xor x="432 128 528 128" f="0" o="5"/>
  <Xor x="304 224 400 224" f="0"/>
  <Xor x="432 240 528 240" f="0"/>
  <Xor x="304 448 400 448" f="0" o="5"/>
  <Xor x="432 464 528 464" f="0" o="5"/>
  <Xor x="656 144 752 144" f="0" o="5"/>
  <L x="624 160 576 160" f="2"/>
  <Xor x="656 256 752 256" f="0"/>
  <L x="624 272 576 272" f="2"/>
  <Xor x="656 368 752 368" f="0"/>
  <L x="624 384 576 384" f="2"/>
  <Xor x="656 480 752 480" f="0" o="5"/>
  <L x="624 496 576 496" f="2"/>
  <Xor x="656 592 752 592" f="0"/>
  <L x="624 608 576 608" f="2" p="1"/>
  <Xor x="656 704 752 704" f="0"/>
  <L x="624 720 576 720" f="2"/>
  <Xor x="656 816 752 816" f="0"/>
  <L x="624 832 576 832" f="2"/>
  <Xor x="1056 128 1152 128" f="0" o="5"/>
  <Xor x="1184 144 1280 144" f="0" o="5"/>
  <Xor x="1312 160 1408 160" f="0" o="5"/>
  <Xor x="1056 288 1152 288" f="0"/>
  <Xor x="1184 304 1280 304" f="0"/>
  <Xor x="1312 320 1408 320" f="0"/>
  <Xor x="1056 448 1152 448" f="0" o="5"/>
  <Xor x="1184 464 1280 464" f="0" o="5"/>
  <Xor x="1312 480 1408 480" f="0" o="5"/>
  <dmux x="1536 128 1696 128" f="0" se="3"/>
  <L x="1536 128 1488 128" f="2" p="1"/>
  <M x="1440 144 1440 96" f="2"/>
  <M x="1440 304 1440 256" f="2"/>
  <M x="1440 464 1440 416" f="2"/>
  <M x="1792 128 1840 128" f="2"/>
  <M x="1792 160 1840 160" f="2"/>
  <M x="1792 192 1840 192" f="2"/>
  <M x="1792 224 1840 224" f="2"/>
  <M x="1792 256 1840 256" f="2"/>
  <M x="1792 288 1840 288" f="2"/>
  <M x="1792 320 1840 320" f="2"/>
  <M x="1792 352 1840 352" f="2"/>
  <Xor x="1808 560 1904 560" f="0"/>
  <M x="1952 560 2000 560" f="2"/>
  <Xor x="1808 624 1904 624" f="0" o="5"/>
  <M x="1952 624 2000 624" f="2"/>
  <Xor x="1808 688 1904 688" f="0"/>
  <M x="1952 688 2000 688" f="2"/>
  <Xor x="1808 752 1904 752" f="0"/>
  <M x="1952 752 2000 752" f="2"/>
  <w x="96 96 304 96" f="0"/>
  <w x="96 208 304 208" f="0"/>
  <w x="96 352 656 352" f="0"/>
  <w x="96 64 96 96" f="0"/>
  <w x="96 96 96 208" f="0"/>
  <w x="96 208 96 352" f="0"/>
  <w x="144 128 304 128" f="0"/>
  <w x="144 432 304 432" f="0"/>
  <w x="144 576 656 576" f="0"/>
  <w x="144 64 144 128" f="0"/>
  <w x="144 128 144 432" f="0"/>
  <w x="144 432 144 576" f="0"/>
  <w x="240 144 432 144" f="0"/>
  <w x="240 256 432 256" f="0"/>
  <w x="240 480 432 480" f="0"/>
  <w x="240 800 656 800" f="0"/>
  <w x="240 64 240 144" f="0"/>
  <w x="240 144 240 256" f="0"/>
  <w x="240 256 240 480" f="0"/>
  <w x="240 480 240 800" f="0"/>
  <w x="400 112 432 112" f="0"/>
  <w x="528 128 656 128" f="0"/>
  <w x="192 240 304 240" f="0"/>
  <w x="192 464 304 464" f="0"/>
  <w x="192 688 656 688" f="0"/>
  <w x="192 64 192 240" f="0"/>
  <w x="192 240 192 464" f="0"/>
  <w x="192 464 192 688" f="0"/>
  <w x="400 224 432 224" f="0"/>
  <w x="528 240 656 240" f="0"/>
  <w x="400 448 432 448" f="0"/>
  <w x="528 464 656 464" f="0"/>
  <w x="624 160 656 160" f="0"/>
  <w x="624 272 656 272" f="0"/>
  <w x="624 384 656 384" f="0"/>
  <w x="624 496 656 496" f="0"/>
  <w x="624 608 656 608" f="0"/>
  <w x="624 720 656 720" f="0"/>
  <w x="624 832 656 832" f="0"/>
  <w x="752 144 816 144" f="0"/>
  <w x="816 112 1056 112" f="0"/>
  <w x="816 112 816 144" f="0"/>
  <w x="752 256 848 256" f="0"/>
  <w x="848 272 1056 272" f="0"/>
  <w x="848 256 848 272" f="0"/>
  <w x="752 368 880 368" f="0"/>
  <w x="880 144 1056 144" f="0"/>
  <w x="880 304 1056 304" f="0"/>
  <w x="880 544 1808 544" f="0"/>
  <w x="880 144 880 304" f="0"/>
  <w x="880 304 880 368" f="0"/>
  <w x="880 368 880 544" f="0"/>
  <w x="752 480 912 480" f="0"/>
  <w x="912 432 1056 432" f="0"/>
  <w x="912 432 912 480" f="0"/>
  <w x="752 592 944 592" f="0"/>
  <w x="944 160 1184 160" f="0"/>
  <w x="944 464 1056 464" f="0"/>
  <w x="944 608 1808 608" f="0"/>
  <w x="944 160 944 464" f="0"/>
  <w x="944 464 944 592" f="0"/>
  <w x="944 592 944 608" f="0"/>
  <w x="752 704 976 704" f="0"/>
  <w x="976 320 1184 320" f="0"/>
  <w x="976 480 1184 480" f="0"/>
  <w x="976 672 1808 672" f="0"/>
  <w x="976 320 976 480" f="0"/>
  <w x="976 480 976 672" f="0"/>
  <w x="976 672 976 704" f="0"/>
  <w x="752 816 1008 816" f="0"/>
  <w x="1008 176 1312 176" f="0"/>
  <w x="1008 336 1312 336" f="0"/>
  <w x="1008 496 1312 496" f="0"/>
  <w x="1008 736 1808 736" f="0"/>
  <w x="1008 176 1008 336" f="0"/>
  <w x="1008 336 1008 496" f="0"/>
  <w x="1008 496 1008 736" f="0"/>
  <w x="1008 736 1008 816" f="0"/>
  <w x="1152 128 1184 128" f="0"/>
  <w x="1280 144 1312 144" f="0"/>
  <w x="1152 288 1184 288" f="0"/>
  <w x="1280 304 1312 304" f="0"/>
  <w x="1152 448 1184 448" f="0"/>
  <w x="1280 464 1312 464" f="0"/>
  <w x="1408 160 1440 160" f="0"/>
  <w x="1440 160 1456 160" f="0"/>
  <w x="1456 160 1456 432" f="0"/>
  <w x="1456 432 1568 432" f="0"/>
  <w x="1568 416 1568 432" f="0"/>
  <w x="1440 144 1440 160" f="0"/>
  <w x="1408 320 1440 320" f="0"/>
  <w x="1440 320 1472 320" f="0"/>
  <w x="1472 320 1472 448" f="0"/>
  <w x="1472 448 1600 448" f="0"/>
  <w x="1600 416 1600 448" f="0"/>
  <w x="1440 304 1440 320" f="0"/>
  <w x="1408 480 1440 480" f="0"/>
  <w x="1440 480 1488 480" f="0"/>
  <w x="1488 464 1488 480" f="0"/>
  <w x="1488 464 1632 464" f="0"/>
  <w x="1632 416 1632 464" f="0"/>
  <w x="1440 464 1440 480" f="0"/>
  <w x="1696 128 1792 128" f="0"/>
  <w x="1696 160 1792 160" f="0"/>
  <w x="1696 192 1792 192" f="0"/>
  <w x="1696 224 1760 224" f="0"/>
  <w x="1760 224 1792 224" f="0"/>
  <w x="1760 224 1760 576" f="0"/>
  <w x="1760 576 1808 576" f="0"/>
  <w x="1696 256 1792 256" f="0"/>
  <w x="1696 288 1744 288" f="0"/>
  <w x="1744 288 1792 288" f="0"/>
  <w x="1744 288 1744 640" f="0"/>
  <w x="1744 640 1808 640" f="0"/>
  <w x="1696 320 1728 320" f="0"/>
  <w x="1728 320 1792 320" f="0"/>
  <w x="1728 320 1728 704" f="0"/>
  <w x="1728 704 1808 704" f="0"/>
  <w x="1696 352 1712 352" f="0"/>
  <w x="1712 352 1792 352" f="0"/>
  <w x="1712 352 1712 768" f="0"/>
  <w x="1712 768 1808 768" f="0"/>
  <w x="1904 560 1952 560" f="0"/>
  <w x="1904 624 1952 624" f="0"/>
  <w x="1904 688 1952 688" f="0"/>
  <w x="1904 752 1952 752" f="0"/>
  <x x="91 -12 101 -9" f="0" si="16" te="A"/>
  <x x="139 -12 149 -9" f="0" si="16" te="B"/>
  <x x="187 -12 198 -9" f="0" si="16" te="C"/>
  <x x="235 -12 246 -9" f="0" si="16" te="D"/>
  <x x="538 166 558 169" f="0" si="16" te="flip"/>
  <x x="594 122 626 125" f="0" si="16" te="1 Y1"/>
  <x x="758 138 776 141" f="0" si="16" te="Z1"/>
  <x x="538 278 558 281" f="0" si="16" te="flip"/>
  <x x="594 234 626 237" f="0" si="16" te="2 Y2"/>
  <x x="758 250 776 253" f="0" si="16" te="Z2"/>
  <x x="538 390 558 393" f="0" si="16" te="flip"/>
  <x x="594 346 618 349" f="0" si="16" te="3 A"/>
  <x x="758 362 776 365" f="0" si="16" te="Z3"/>
  <x x="538 502 558 505" f="0" si="16" te="flip"/>
  <x x="594 458 626 461" f="0" si="16" te="4 Y4"/>
  <x x="758 474 776 477" f="0" si="16" te="Z4"/>
  <x x="538 614 558 617" f="0" si="16" te="flip"/>
  <x x="594 570 618 573" f="0" si="16" te="5 B"/>
  <x x="758 586 776 589" f="0" si="16" te="Z5"/>
  <x x="538 726 558 729" f="0" si="16" te="flip"/>
  <x x="594 682 618 685" f="0" si="16" te="6 C"/>
  <x x="758 698 776 701" f="0" si="16" te="Z6"/>
  <x x="538 838 558 841" f="0" si="16" te="flip"/>
  <x x="594 794 618 797" f="0" si="16" te="7 D"/>
  <x x="758 810 776 813" f="0" si="16" te="Z7"/>
  <x x="1456 104 1520 107" f="0" si="16" te="fixed at 1"/>
  <x x="1548 88 1773 91" f="0" si="16" te="demultiplexer as 3-to-8 decoder"/>
  <x x="1406 102 1426 105" f="0" si="16" te="R1"/>
  <x x="1406 262 1426 265" f="0" si="16" te="R2"/>
  <x x="1406 422 1426 425" f="0" si="16" te="R4"/>
  <x x="1860 134 1933 137" f="0" si="16" te="0: no error"/>
  <x x="1860 166 1929 169" f="0" si="16" te="1: flip at 1"/>
  <x x="1860 198 1929 201" f="0" si="16" te="2: flip at 2"/>
  <x x="1860 230 1929 233" f="0" si="16" te="3: flip at 3"/>
  <x x="1860 262 1929 265" f="0" si="16" te="4: flip at 4"/>
  <x x="1860 294 1929 297" f="0" si="16" te="5: flip at 5"/>
  <x x="1860 326 1929 329" f="0" si="16" te="6: flip at 6"/>
  <x x="1860 358 1929 361" f="0" si="16" te="7: flip at 7"/>
  <x x="2020 566 2100 569" f="0" si="16" te="A corrected"/>
  <x x="2020 630 2101 633" f="0" si="16" te="B corrected"/>
  <x x="2020 694 2102 697" f="0" si="16" te="C corrected"/>
  <x x="2020 758 2102 761" f="0" si="16" te="D corrected"/>
</cir>

Wattsinside