The Central Idea

Digital information is represented by finite strings of symbols.

In binary systems, those symbols are

\[ \boxed{0\text{ and }1}. \]

If a bit changes accidentally during storage or transmission, the received string may differ from the original.

Error-detection methods add extra structure so that some altered strings can be recognized as invalid.

Bit

A bit is a binary digit.

It can take one of two values:

\[ 0 \]

or

\[ 1. \]

A sequence of bits is called a binary string, bit string, or binary word.

Binary Words

Examples of binary words include

\[ 0, \] \[ 101, \] \[ 11001001. \]

The number of bits in the word is its length.

For example,

\[ |11001001|=8. \]

How Many Binary Words Have Length \(n\)?

Each bit position has two possible values.

Therefore, the number of binary words of length \(n\) is

\[ \boxed{2^n}. \]

For \(8\) bits,

\[ 2^8=256 \]

distinct bit patterns are possible.

Bits Can Represent Many Kinds of Information

A bit pattern can represent:

The interpretation depends on the encoding convention.

Representation Is a Mapping

A digital encoding assigns meanings to finite bit patterns.

Conceptually,

\[ \boxed{\text{information}\longleftrightarrow\text{bit pattern}}. \]

The same bit pattern can represent different things under different conventions.

Binary Representation of Nonnegative Integers

A binary numeral

\[ b_{n-1}b_{n-2}\cdots b_1b_0 \]

represents

\[ b_{n-1}2^{n-1} + b_{n-2}2^{n-2} +\cdots+ b_12 + b_0, \]

where each

\[ b_i\in\{0,1\}. \]

Example: Binary to Decimal

The binary numeral

\[ 1011_2 \]

represents

\[ 1\cdot2^3 + 0\cdot2^2 + 1\cdot2^1 + 1\cdot2^0. \]

Therefore,

\[ 1011_2 = 8+0+2+1 = \boxed{11_{10}}. \]

Fixed-Length Representation

Digital systems often use words of fixed length.

An unsigned \(n\)-bit word can represent

\[ 2^n \]

distinct patterns.

If used for nonnegative integers beginning at \(0\), the range is

\[ \boxed{0\text{ through }2^n-1}. \]

Example: Eight-Bit Unsigned Range

An \(8\)-bit word has

\[ 2^8=256 \]

possible patterns.

Therefore, an unsigned eight-bit integer can represent

\[ \boxed{0\text{ through }255}. \]

Why Errors Occur

A stored or transmitted bit may be altered by physical effects such as:

Mathematics cannot eliminate every physical fault, but it can help detect many resulting changes.

Bit Error

A bit error occurs when a bit changes:

\[ 0\to1 \]

or

\[ 1\to0. \]

If only one bit changes, the event is called a single-bit error.

Error Detection Requires Redundancy

If every possible \(n\)-bit word is treated as a valid message, then changing one valid word into another valid word cannot be recognized merely from the received bits.

Error detection therefore requires redundancy.

Some possible bit patterns must be reserved as invalid.

Data Bits and Check Bits

Suppose \(k\) bits carry the original information and additional bits are added for checking.

The original bits are often called data bits.

The extra bits are called check bits, redundancy bits, or parity bits depending on the method.

Codeword

A codeword is a bit pattern that satisfies the rules of an error-detecting or error-correcting code.

Not every possible bit pattern needs to be a valid codeword.

This separation between valid and invalid patterns makes error detection possible.

Parity

The parity of a binary word depends on whether the number of \(1\)s is even or odd.

For example,

\[ 1011 \]

contains three \(1\)s, so it has odd parity.

The word

\[ 1010 \]

contains two \(1\)s, so it has even parity.

Even Parity Bit

An even parity bit is chosen so that the total number of \(1\)s in the transmitted word is even.

Suppose the data is

\[ 1011. \]

It contains three \(1\)s.

Add parity bit \(1\) to make the total four:

\[ \boxed{10111}. \]

Odd Parity Bit

An odd parity bit is chosen so that the total number of \(1\)s is odd.

If the data

\[ 1011 \]

already contains three \(1\)s, an odd-parity bit can be

\[ 0. \]

The resulting word remains odd in parity.

Parity as XOR

XOR naturally computes parity.

For bits

\[ b_1,b_2,\ldots,b_n, \]

the XOR

\[ b_1\oplus b_2\oplus\cdots\oplus b_n \]

is \(1\) exactly when an odd number of the inputs are \(1\).

Why Parity Detects a Single-Bit Error

Flipping one bit changes the number of \(1\)s by exactly one.

Therefore, even parity becomes odd, or odd parity becomes even.

The receiver can detect that the parity rule has been violated.

Example: Detecting a Single-Bit Error

Suppose even parity requires

\[ 10111. \]

This word contains four \(1\)s.

If one bit changes and the receiver gets

\[ 10011, \]

the received word contains three \(1\)s.

Even parity has failed, so an error is detected.

Parity Cannot Detect Every Error

If two bits are flipped, the parity may remain unchanged.

For example, an even-parity word can undergo two bit changes and still have an even number of \(1\)s.

Therefore, one parity bit detects every odd number of bit flips but may miss an even number of bit flips.

Error Detection versus Error Correction

Error detection tells us that something is wrong.

Error correction provides enough information to determine what the original valid word should have been.

Detecting an error is generally easier than correcting it.

Why Simple Parity Usually Does Not Correct

If parity fails, we know that an error occurred.

But with only one parity bit, we usually do not know which data bit changed.

Therefore, the original word cannot generally be reconstructed from parity alone.

Hamming Distance

The Hamming distance between two equal-length binary words is the number of positions in which they differ.

It is commonly written

\[ d(x,y). \]

Example: Hamming Distance

Compare

\[ x=101101 \]

and

\[ y=100001. \]

They differ in two positions.

Therefore,

\[ \boxed{d(x,y)=2}. \]

Hamming Distance as Number of Bit Flips

The Hamming distance tells us the minimum number of single-bit flips needed to transform one word into another.

If

\[ d(x,y)=3, \]

then at least three bit changes are required to turn \(x\) into \(y\).

Minimum Distance of a Code

If \(C\) is a set of valid codewords, the minimum distance is the smallest Hamming distance between any two distinct valid codewords.

It is often written

\[ d_{\min}. \]

Distance and Error Detection

A code with minimum distance

\[ d_{\min} \]

can detect up to

\[ \boxed{d_{\min}-1} \]

bit errors.

Fewer than \(d_{\min}\) changes cannot transform one valid codeword into a different valid codeword.

Distance and Error Correction

A code with minimum distance \(d_{\min}\) can correct up to

\[ \boxed{ \left\lfloor\frac{d_{\min}-1}{2}\right\rfloor } \]

bit errors using nearest-codeword reasoning.

Why Correction Requires Greater Separation

To correct errors reliably, the received word must be closer to the original codeword than to any other valid codeword.

Larger minimum distance creates a wider separation between valid messages.

Repetition Code

A simple error-correcting idea is to repeat a bit.

For example,

\[ 0\mapsto000, \] \[ 1\mapsto111. \]

The valid codewords are

\[ \{000,111\}. \]

Distance of the Three-Repetition Code

The codewords

\[ 000 \]

and

\[ 111 \]

differ in all three positions.

Therefore,

\[ d_{\min}=3. \]

Correcting One Error by Majority

Suppose

\[ 111 \]

is sent but

\[ 101 \]

is received.

Two of the three bits are \(1\), so majority voting suggests the original bit was

\[ \boxed{1}. \]

The Cost of Redundancy

Redundancy improves reliability but increases the number of transmitted or stored bits.

In the three-repetition code, one information bit requires three physical bits.

Real codes seek better reliability with less overhead.

Code Rate

If \(k\) information bits are encoded into an \(n\)-bit codeword, the code rate is

\[ \boxed{R=\frac{k}{n}}. \]

A higher rate means less redundancy.

A lower rate generally allows more room for error-control information.

Block Codes

A block code encodes fixed-size blocks of data into fixed-size codewords.

Conceptually,

\[ \{0,1\}^k \longrightarrow \{0,1\}^n. \]

The code chooses only some \(n\)-bit words as valid outputs.

Redundancy Creates Invalid Regions

Because only some \(n\)-bit words are valid codewords, an altered transmission may land on an invalid word.

The receiver can then detect that an error occurred.

This is the geometric intuition behind many coding methods.

Parity as a Code

Even parity restricts valid words to those with an even number of \(1\)s.

Half of all binary words have even parity and half have odd parity.

Therefore, parity discards half the possible words as invalid.

Parity Code Minimum Distance

Two valid even-parity words cannot differ in exactly one bit, because one bit flip changes parity.

The minimum distance is therefore at least \(2\).

In the ordinary single-parity code,

\[ \boxed{d_{\min}=2}. \]

Thus it detects one bit error but cannot generally correct one.

Checksums

A checksum is a compact value computed from a larger block of data and stored or transmitted with it.

The receiver recomputes the checksum and compares the result.

A mismatch indicates that the data has changed.

Simple Modular Checksum Idea

Suppose data values are

\[ a_1,a_2,\ldots,a_n. \]

A simple checksum might compute

\[ \boxed{ c\equiv a_1+a_2+\cdots+a_n \pmod m }. \]

The receiver recomputes the same modular sum.

Checksums Are Not Perfect

Different altered data blocks can sometimes produce the same checksum.

Therefore, a checksum detects many errors but not every possible error.

The strength depends on the checksum design.

Hash-Like Error Detection

More sophisticated systems compute a larger summary value from the data.

If the data changes, the summary is likely to change as well.

At an introductory level, the key idea is the same:

\[ \boxed{\text{data}\longrightarrow\text{check value}}. \]

Parity in Two Dimensions

Bits can be arranged in rows and columns with parity checks for each row and each column.

A single-bit error may then violate one row parity and one column parity.

Their intersection can identify the altered bit.

Example of Two-Dimensional Parity

Suppose a block is arranged as a rectangular array.

Add an even-parity bit to every row and every column.

If one data bit flips, exactly one row check and one column check typically fail.

The intersection locates the error.

Error Detection through Structure

Parity, checksums, and coding methods all use the same general principle:

\[ \boxed{\text{valid data must satisfy extra mathematical relationships}}. \]

An error is detectable when the altered data violates those relationships.

Detectable Error Pattern

An error pattern is detectable if applying it to a valid codeword cannot produce another valid codeword.

Minimum-distance reasoning gives a general way to guarantee detection of bounded numbers of bit errors.

Undetectable Error Pattern

An error is undetectable when one valid codeword is changed into another valid codeword.

The receiver sees a valid pattern and therefore has no purely structural reason to suspect corruption.

Noise and Channels

In communication theory, the mechanism carrying information from sender to receiver is called a channel.

Noise may alter the transmitted symbols.

Error-control coding adds redundancy before transmission so that the receiver can detect or correct some channel errors.

Encoding and Decoding

An encoder maps data into valid codewords.

A decoder examines the received word and attempts to:

Finite Sets Make Coding Possible to Analyze

For fixed word length \(n\), there are only

\[ 2^n \]

possible received words.

A code selects a finite subset of these as valid codewords.

This makes error behavior a finite combinatorial problem.

Example: A Tiny Code

Consider

\[ C=\{0000,1111\}. \]

The two valid codewords have Hamming distance

\[ d(0000,1111)=4. \]

Thus,

\[ d_{\min}=4. \]

Detection Ability of the Tiny Code

Since

\[ d_{\min}=4, \]

the code can detect up to

\[ d_{\min}-1=3 \]

bit errors.

Correction Ability of the Tiny Code

The number of guaranteed correctable errors is

\[ \left\lfloor\frac{4-1}{2}\right\rfloor = \left\lfloor\frac32\right\rfloor = 1. \]

Therefore, the code can guarantee correction of one bit error.

Digital Representation and Logic

Error checks are often implemented using Boolean operations.

XOR gates can compute parity.

AND and OR gates can combine error flags.

Finite-state systems can track communication states and protocol progress.

Thus the topics in this unit connect directly.

Error Flags

A digital system may produce a Boolean signal

\[ e= \begin{cases} 1,&\text{if an error is detected},\\ 0,&\text{otherwise}. \end{cases} \]

Such flags can control retries, warnings, or rejection of corrupted data.

Retransmission

Detection alone can still be useful when a sender can retransmit data.

A receiver may:

  1. check the received data;
  2. detect corruption;
  3. request another copy.

In such systems, correction need not always occur locally.

Reliability Is a Design Tradeoff

More redundancy can improve error protection.

But additional bits also require more:

Digital systems balance efficiency against reliability.

Common Error: Confusing a Bit with a Boolean Meaning

A bit is the symbol \(0\) or \(1\).

Its interpretation depends on the encoding.

A \(1\) might mean true, active, high voltage, a numerical contribution, or something else.

Common Error: Confusing Detection with Correction

Detecting an error does not automatically identify the altered bit.

Correction requires enough additional structure to infer the intended codeword.

Common Error: Assuming Parity Detects Every Error

One parity bit reliably detects any odd number of bit flips.

It may fail to detect an even number of bit flips.

Common Error: Counting Matching Bits for Hamming Distance

Hamming distance counts positions that differ.

It does not count positions that match.

Common Error: Comparing Words of Different Lengths

Standard Hamming distance applies to words of equal length.

Each position in one word is compared with the corresponding position in the other.

Common Error: Assuming More Redundancy Is Free

Extra check bits improve reliability only by using additional resources.

Redundancy always creates some overhead.

Common Error: Treating a Checksum as Proof of Correctness

A matching checksum provides evidence that no detectable change occurred.

It does not guarantee that two different data blocks could never share the same checksum.

A Reliable Procedure for Adding Even Parity

  1. Count the number of \(1\)s in the data bits.
  2. If the count is already even, add parity bit \(0\).
  3. If the count is odd, add parity bit \(1\).
  4. Check that the complete word contains an even number of \(1\)s.

A Reliable Procedure for Checking Parity

  1. Count the \(1\)s in the received word.
  2. Compare the parity with the required convention.
  3. If the parity rule is violated, report a detected error.
  4. If the parity rule holds, report only that no parity-detectable error was found.

A Reliable Procedure for Hamming Distance

  1. Write the equal-length words one above the other.
  2. Compare corresponding positions.
  3. Mark every position where the bits differ.
  4. Count the marked positions.
  5. The count is the Hamming distance.

A Reliable Procedure for Reading a Code’s Error Ability

  1. Determine the minimum distance \(d_{\min}\).
  2. Guaranteed detectable errors equal \(d_{\min}-1\).
  3. Guaranteed correctable errors equal \(\left\lfloor(d_{\min}-1)/2\right\rfloor\).
  4. Distinguish guaranteed performance from errors that may happen to be detected anyway.

Example: Full Parity Workflow

Add an even-parity bit to

\[ 1101010. \]

Count the \(1\)s:

\[ 1+1+0+1+0+1+0 \]

gives four \(1\)s.

Four is already even, so the parity bit is

\[ 0. \]

One possible transmitted word is

\[ \boxed{11010100}. \]

Example: Full Hamming-Distance Workflow

Find the distance between

\[ 110101 \]

and

\[ 100111. \]

Compare position by position:

Position 1 2 3 4 5 6
First word 110101
Second word 100111
Different? NoYesNoNoYesNo

Two positions differ, so

\[ \boxed{d(110101,100111)=2}. \]

Practice 1: Number of Bit Patterns

How many distinct \(6\)-bit words exist?

Practice 2: Binary Value

Convert

\[ 1010_2 \]

to decimal.

Practice 3: Even Parity

What parity bit should be added to

\[ 1010 \]

to produce even parity?

Practice 4: Odd Parity

What parity bit should be added to

\[ 1110 \]

to produce odd parity?

Practice 5: Hamming Distance

Find

\[ d(1011,1110). \]

Practice 6: Single-Bit Detection

Can ordinary even parity detect every single-bit error?

Practice 7: Two-Bit Error

Can ordinary parity fail to detect a two-bit error?

Practice 8: Minimum Distance

A code has

\[ d_{\min}=4. \]

How many bit errors can it guarantee to detect?

Practice 9: Error Correction

A code has

\[ d_{\min}=5. \]

How many bit errors can it guarantee to correct?

Practice 10: Repetition Code

In the three-repetition code, the receiver gets

\[ 010. \]

Which original bit would majority decoding select?

Practice Answers

Practice 1

\[ 2^6=64. \]

Therefore,

\[ \boxed{64}. \]

Practice 2

\[ 1010_2 = 1\cdot8 + 0\cdot4 + 1\cdot2 + 0\cdot1 = 10. \]

Therefore,

\[ \boxed{1010_2=10_{10}}. \]

Practice 3

The word \(1010\) contains two \(1\)s, which is already even.

Therefore, add

\[ \boxed{0}. \]

Practice 4

The word \(1110\) contains three \(1\)s, which is already odd.

Therefore, add

\[ \boxed{0}. \]

Practice 5

Compare

\[ 1011 \]

and

\[ 1110. \]

They differ in the second and fourth positions.

\[ \boxed{d(1011,1110)=2}. \]

Practice 6

Yes.

One bit flip always changes parity.

Practice 7

Yes.

Two flips can preserve the original parity.

Practice 8

\[ d_{\min}-1=4-1=3. \]

Therefore,

\[ \boxed{3\text{ bit errors}}. \]

Practice 9

\[ \left\lfloor\frac{5-1}{2}\right\rfloor = \left\lfloor2\right\rfloor = 2. \]

Therefore,

\[ \boxed{2\text{ bit errors}}. \]

Practice 10

The word

\[ 010 \]

contains two \(0\)s and one \(1\).

Majority decoding selects

\[ \boxed{0}. \]

What to Remember

The central habit is to view error control as a problem of separating valid digital patterns far enough apart that accidental changes can be recognized or corrected.

Where We Go Next

This lesson completes the sequence on logic, Boolean structures, and finite systems. We began with propositions and truth tables, developed Boolean operations and equivalence, organized formulas into normal forms, built circuits and state machines, introduced automata and formal languages, and then used finite logical structure for satisfiability and reliable digital representation.

Together, these ideas form a bridge between mathematical logic, discrete structures, algorithms, digital computation, and information systems.