Error Detection, Error Correction and Flip-Flops

1. Introduction to Error Detection and Correction

When data travels through a communication channel, electrical noise, interference, hardware faults, or transmission problems may change one or more bits. Error-control methods help a receiver detect whether data was damaged and, in some cases, correct the error.

Common Types of Errors

• Single-Bit Error: Only one bit changes from 0 to 1 or from 1 to 0.
• Multiple-Bit Error: More than one bit changes within a data unit.
• Burst Error: A group of bits within a data unit is affected. The bits between the first and last affected positions may or may not all be incorrect.

Error Detection vs Error Correction

2. Redundancy in Data Communication

Error-control techniques add extra information to the original data. This additional information is called redundancy. The receiver uses it to check whether the data changed during transmission.

More redundancy can improve error detection or correction capability, but it also increases the amount of data that must be transmitted.

3. Parity Check

Parity checking is a simple error-detection method. An extra bit, called a parity bit, is added to a data unit so the total number of 1s becomes either even or odd.

Even Parity

In even parity, the parity bit is chosen so that the total number of 1s is even.

Example: Data = 1011. The data contains three 1s, which is odd. For even parity, the parity bit must be 1, making the total number of 1s equal to four.

Odd Parity

In odd parity, the parity bit is chosen so that the total number of 1s is odd.

4. Checksum

A checksum is an error-detection value calculated from a group of data units. The sender includes the checksum with the data, and the receiver recalculates it to check whether the data may have changed.

Checksums are commonly used by communication protocols and storage systems. They can detect many accidental errors, but no checksum method detects every possible kind of error.

General Checksum Process

1. The sender divides data into fixed-size units.
2. The sender calculates a checksum from those units.
3. The checksum is transmitted with the data.
4. The receiver recalculates the checksum from the received data.
5. If the calculated value does not match the expected value, the receiver treats the data as damaged.

5. Cyclic Redundancy Check (CRC)

Cyclic Redundancy Check, or CRC, is a widely used error-detection technique. It uses binary polynomial division to calculate a remainder that is sent with the data.

The sender and receiver use the same agreed generator value. If the received data does not produce the expected result during checking, an error is detected.

Why CRC Is Important

• CRC is effective at detecting many common transmission errors.
• It is especially good at detecting many burst-error patterns.
• It is used in technologies such as Ethernet, storage systems, and communication protocols.
• CRC detects errors but does not normally correct them by itself.

6. Hamming Code

Hamming code is an error-correction technique that adds parity bits to data bits. A standard Hamming code can identify and correct a single-bit error.

Parity-Bit Positions

In a Hamming code, parity bits are placed at positions that are powers of two: 1, 2, 4, 8, and so on.

If a message contains m data bits and requires r parity bits, the following condition is used for single-bit error correction:

2^r ≥ m + r + 1

The receiver checks parity groups. The combined result identifies the location of a single-bit error, allowing the receiver to correct it.

SEC and SECDED

• SEC: Single Error Correction.
• SECDED: Single Error Correction, Double Error Detection. This commonly adds an overall parity bit to a Hamming code.

7. Retransmission and ARQ

Some systems detect an error and ask the sender to retransmit the affected data. This approach is called Automatic Repeat Request (ARQ).

• Stop-and-Wait ARQ: The sender transmits one frame and waits for an acknowledgement before sending the next frame.
• Go-Back-N ARQ: The sender may send multiple frames. When an error or loss occurs, the sender retransmits the affected frame and later unacknowledged frames.
• Selective Repeat ARQ: The receiver can accept correctly received frames and request retransmission of only missing or damaged frames.

Forward Error Correction

Forward Error Correction adds enough redundant information for a receiver to correct some errors without asking for retransmission. It is useful when retransmission is expensive or impractical, such as some wireless, satellite, or real-time communication systems.

8. Introduction to Flip-Flops

A flip-flop is a fundamental sequential logic circuit that stores one bit of binary information. Its two stable states represent logic 0 and logic 1.

Flip-flops are used in registers, counters, memory-related circuits, state machines, timing circuits, and digital control systems.

Characteristics of Flip-Flops

• Bistable Device: Has two stable states.
• Memory Element: Stores one bit of information.
• Sequential Circuit: Its output depends on present inputs and previous state.
• Clock-Controlled: Many flip-flops change state in response to a clock edge.
• Complementary Outputs: Q and Q' are normally complements of each other.

9. Latch vs Flip-Flop

10. Types of Flip-Flops

11. SR Flip-Flop

SR stands for Set-Reset. A conventional active-high SR flip-flop has two inputs: Set (S) and Reset (R).

Characteristic Equation: Q_next = S + R'Q

12. JK Flip-Flop

The JK flip-flop improves on the SR flip-flop by removing its invalid state. When J = K = 1, the output toggles.

Characteristic Equation: Q_next = JQ' + K'Q

Race-Around Condition

In a level-triggered JK flip-flop, when J = K = 1 and the clock pulse remains active for too long, the output can toggle repeatedly during the same clock period. This is called the race-around condition.

Ways to Avoid Race-Around

• Use an edge-triggered JK flip-flop.
• Use a master-slave JK flip-flop.
• Use a suitably short clock pulse.

13. D Flip-Flop

D stands for Data or Delay. A D flip-flop transfers the value at D to Q at the active clock edge.

Characteristic Equation: Q_next = D

Construction Using JK Flip-Flop

A D flip-flop can be created from a JK flip-flop by connecting: J = D and K = D'.

Applications

• Registers and temporary storage
• Pipeline registers
• Shift registers
• Signal synchronisation
• State storage in sequential circuits

14. T Flip-Flop

T stands for Toggle. A T flip-flop changes state when T = 1 and retains its previous state when T = 0.

Characteristic Equation: Q_next = T ⊕ Q

Equivalent form: Q_next = TQ' + T'Q

Construction Using JK Flip-Flop

A T flip-flop can be created from a JK flip-flop by connecting: J = K = T.

Applications

• Binary counters
• Frequency division
• Toggle circuits
• Sequential state transitions

15. Master-Slave Flip-Flop

A master-slave flip-flop uses two storage stages connected in cascade. The first stage is called the master, and the second is called the slave.

1. The master receives input during one clock phase.
2. The slave remains isolated during that phase.
3. During the opposite clock phase, the master stops accepting new input.
4. The slave receives the master's stored state.
5. The output changes in a controlled manner.

Master-slave designs help reduce race-around problems in JK flip-flops.

16. Characteristic Equations

17. Flip-Flop Excitation Tables

An excitation table shows the input values required to change a flip-flop from its present state Q to a desired next state Q_next. In these tables, X means “don't care.”

SR Flip-Flop Excitation Table

JK Flip-Flop Excitation Table

D and T Flip-Flop Excitation Table

18. Comparison of Flip-Flops

19. Quick Revision

• Parity checking detects odd numbers of bit errors but cannot correct errors.
• CRC is a powerful error-detection technique, especially for many burst errors.
• Hamming code can correct a single-bit error.
• ARQ uses acknowledgements, error detection, and retransmission.
• Flip-flops store one bit of information.
• SR means Set-Reset, JK can toggle, D stores data, and T toggles.
• For a JK flip-flop, J = K = 1 causes toggling.
• For a T flip-flop, T = 0 gives no change and T = 1 causes toggling.
• D flip-flops are widely used in registers and storage circuits.
• Race-around can occur in a level-triggered JK flip-flop when J = K = 1.