Binary Codes

Code: A prescription for a unique mapping (coding) of symbols from one set (source) to another set (target)
- The mapping must not be reversible
- A code-word (string) is a character sequence
- A code specifies how we interpret character sequences
Goal: Optimizing processing, information exchange, fault tolerance, storage, and security

Analog/Digital Conversion

Conversion of continuous (real) signals into combined binary signals
Task: Find a unique mapping continuous space → binary set
- Small changes in the continuous space should lead to small changes in the binary set
- Prevent negative intermediate representations

Hamming distance: Number of different positions between two binary code-words
Minimum hamming distance: is the smallest hamming distance between all possible pairs in a set
Incrementing codes: Code where the hamming distance between two neighbor words is always 1

Binary numbers
Reflected Binary Code
- Recursive mapping for n-bit codes
- An incrementing code
- $G_{n + 1} = {0 G_{n}, 1 G_{n}^{re f}}; G_{1} = 0, 1; n \geq 1$
- Constructed through reflection of row from the middle. The results is appended to 0 and 1 to form the next words

Goal: Mapping of lexical arrangement of code-words from a source character set to a lexical arrangement of binary code-words

ASCII (American Standard Code for Information Interchange)
- 7-bit codes (represents 128 characters)
- Sufficient for english language and some special characters
Unicode
- 16-bit codes (represents 65536 characters)
- ASCII extension (first 128 characters of unicode is ascii)
- Includes support for more languages and symbols
Binary Coded Decimal (BCD, 8-4-2-1)
- Digit wise conversion of a decimal number into a four bit binary numbers
- Used for displaying on 7 segment displays
- Versions
  - Unpacked: uses a byte for each decimal position → upper 4 bits are filled with 0s
  - Packed: uses a nibble (4 bits) for each decimal digit
- Advantages
  - Simple and fast conversions
- Drawbacks
  - Wasteful
  - Arithmetic is more complex (when a single digit >9, a correction via adding and additional 6 to that digit is necessary)

Faults are common in system and can have various sources (fabrication, crosstalk, outside influence such as radiation)
Fault Detection
- Want to know if a code word is faulty
- Requires sending again if faulty
- Example: Parity bit
Fault Correcting
- Want to know which bit is faulty
- Example: Group codes, cyclic codes, convolutional codes, crc
General Idea
- Fix the maximum number of faults that can be simultaneously detected
  - In general, maximum 1-2 bits
- Inclusion of redundant information binary code-word
- Mapping is constructed such that faults are mapped to code words that are not used for the coding
- Faults are detected when redundant code-words appear
Possibility
- 1-bit bit fault detections in codes with minimal hamming distance 2
- 2-bit fault detection or 1-bit fault correction if minimal hamming distance is 3
Parity Representation
- Parity $P (x)$ of a code-word X = number of 1s in X
  - P(x)=0 → even parity. The number of 1s is even
  - P(x)=1 → odd parity. The number of 1s is odd
- Method
  - Computer and append the parity bit to the code word
  - The receiver performs fault detection through parity check
  - In case of single bit fault, the parity bit changes which leads to the detection of a fault
- Can do parity bits across both columns and rows (sending the parities across columns as a checksum at the end) to be able to detect which bit had a fault and correct it