Hamming's [7,4] code

Error

There was an error loading the page.

Contributors

Feedback

From users who are members of Content created by Newcastle University :

Newcastle University Mathematics and Statistics

said

Ready to use

6 years, 8 months ago

History

○

Christian Lawson-Perfect 6 years, 8 months ago

Published this.

○

Newcastle University Mathematics and Statistics 6 years, 8 months ago

Gave some feedback: Ready to use

○

Christian Lawson-Perfect 6 years, 8 months ago

Created this.

There is only one version of this question that you have access to.

There is one other version that you do not have access to.

Question statement

A binary string was encoded using the binary Hamming $[7,4]$ code defined by (and encoded using) check digits, and then transmitted.

The string $\var{received}$ was received.

Give any introductory information the student needs.

			Name	Type	Generated Value

num_codewords	integer	2
original_words	list	List of 2 items
original	codeword	codeword("10100101",2)
encoded_words	list	List of 2 items
error_positions	list	[ 5, 1 ]
received_words	list	List of 2 items
received	codeword	codeword("10110000000101",2)
word_parity_checks	list	List of 2 items
word_error_positions	list	[ 6, 2 ]

Automatically regenerate variables?

Name

Data type

Value

xxxxxxxxxx
 
2

JME function reference

Description

The number of words in the message

Describe what this variable represents, and list any assumptions made about its value.

Can an exam override the value of this variable?

Generated value: `integer`

→ Used by:

error_positions
original_words
received_words

Advice

Parts

Gap-fill
1. Gap Match text pattern
  Add

Gap-fill

Ask the student a question, and give any hints about how they should answer this part.

Assuming that the received message contains at most one error per codeword, correct any errors, and then decode to find the original binary string.

Original message: Unnamed gap

Advice

The message we received has $\var{len(received)}$ digits. Each codeword in Hamming's $[7,4]$ code is $7$ digits long, so we have received $\var{num_codewords}$ words.

For each word, calculate the parity checks to establish if, and where, any error has occurred.

Decoding the received word $\var{received_words[0]}$

Let $d_1d_2d_3d_4d_5d_6d_7 = \var{received_words[0]}$. The parity checks give

\begin{align}
c_1 &= d_1 + d_3 + d_5 + d_7 = \simplify[]{{received_words[0][0]}+{received_words[0][2]}+{received_words[0][4]}+{received_words[0][6]}} = \var{word_parity_checks[0][2]} \\
c_2 &= d_2 + d_3 + d_6 + d_7 = \simplify[]{{received_words[0][1]}+{received_words[0][2]}+{received_words[0][5]}+{received_words[0][6]}} = \var{word_parity_checks[0][1]} \\
c_4 &= d_4 + d_5 + d_6 + d_7 = \simplify[]{{received_words[0][3]}+{received_words[0][4]}+{received_words[0][5]}+{received_words[0][6]}} = \var{word_parity_checks[0][0]} \\
\end{align}

So the checking number is $c_4c_2c_1 = \var{word_parity_checks[0]}$, which is binary for $\simplify[]{{4*word_parity_checks[0][0]}+{2*word_parity_checks[0][1]}+{1*word_parity_checks[0][2]}} = \var{word_error_positions[0]}$. {error_explanation(word_error_positions[0],encoded_words[0])}

We then delete the check digits (the first, second and fourth digits) to obtain the decoded word $\var{original_words[0]}$.

Decoding the received word $\var{received_words[1]}$

Let $d_1d_2d_3d_4d_5d_6d_7 = \var{received_words[1]}$. The parity checks give

\begin{align}
c_1 &= d_1 + d_3 + d_5 + d_7 = \simplify[]{{received_words[1][0]}+{received_words[1][2]}+{received_words[1][4]}+{received_words[1][6]}} = \var{word_parity_checks[1][2]} \\
c_2 &= d_2 + d_3 + d_6 + d_7 = \simplify[]{{received_words[1][1]}+{received_words[1][2]}+{received_words[1][5]}+{received_words[1][6]}} = \var{word_parity_checks[1][1]} \\
c_4 &= d_4 + d_5 + d_6 + d_7 = \simplify[]{{received_words[1][3]}+{received_words[1][4]}+{received_words[1][5]}+{received_words[1][6]}} = \var{word_parity_checks[1][0]} \\
\end{align}

So the checking number is $c_4c_2c_1 = \var{word_parity_checks[1]}$, which is binary for $\simplify[]{{4*word_parity_checks[1][0]}+{2*word_parity_checks[1][1]}+{1*word_parity_checks[1][2]}} = \var{word_error_positions[1]}$. {error_explanation(word_error_positions[1],encoded_words[1])}

We then delete the check digits (the first, second and fourth digits) to obtain the decoded word $\var{original_words[1]}$.

Putting the two decoded words together, we obtain the decoded message $\var{original}$.

Give a worked solution to the whole question.

Use this tab to check that this question works as expected.

There was an error which means the tests can't run:

Part	Test	Passed?
Gap-fill
Gap-fill		Hasn't run yet
Match text pattern
Match text pattern		Hasn't run yet

This question is used in the following exams:

Loading...

Error

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Christian Lawson-Perfect 6 years, 8 months ago

Newcastle University Mathematics and Statistics 6 years, 8 months ago

Christian Lawson-Perfect 6 years, 8 months ago

Error in variable testing condition

Error

Warning

Generated value: `integer`

Parts

Gap-fill

Decoding the received word $\var{received_words[0]}$

Decoding the received word $\var{received_words[1]}$

Loading...

Error

Hamming's [7,4] code

Metadata

Taxonomy: mathcentre

Taxonomy: Kind of activity

Taxonomy: Context

Contributors

Feedback

History

Comment

Checkpoint description

Christian Lawson-Perfect 6 years, 8 months ago

Newcastle University Mathematics and Statistics 6 years, 8 months ago

Christian Lawson-Perfect 6 years, 8 months ago

Error in variable testing condition

Error

Warning

Generated value: integer

Parts

Gap-fill

Decoding the received word $\var{received_words[0]}$

Decoding the received word $\var{received_words[1]}$

Generated value: `integer`