Coding‑Decoding – Study Notes
Prepared for the West Bengal Police Sub‑Inspector (SI) Reasoning Ability Test
(MIT‑level, first‑principles treatment with rigorous reasoning and edge‑case analysis)
1. Introduction
Coding‑decoding problems test the ability to:
| Goal | Typical Question |
|---|---|
| Encode a given English string into a coded form | “Encode the word DECODE using the rule ‘shift each letter by 3’.” |
| Decode a given coded string into the original | “Decode the string 1‑2‑3‑4‑5 using the rule ‘map 1→A, 2→B…’.” |
| Find the rule from two example pairs | “Given C → 01, D → 100, find the rule that maps a letter to a binary string.” |
Why it matters for the SI exam
- Quick pattern recognition under a time limit.
- Logical deduction from limited information.
- Ability to spot hidden constraints (e.g., one‑to‑one mapping).
2. From First Principles
2.1 Coding‑Decoding as a Function
Let
- (S) = source alphabet (e.g., English letters).
- (C) = coded alphabet (could be numbers, symbols, binary strings).
A coding function (f: S \rightarrow C).
A decoding function (f^{-1}: C \rightarrow S) exists iff (f) is bijective (injective + surjective).
Key observations
- Injective → no two letters map to the same code.
- Surjective → every code in (C) corresponds to some letter in (S).
- If the mapping is partial (not all letters used), we may still decode any code that appears in the given instance.
2.2 Types of Coding Schemes
| Scheme | Example | Mathematical View |
|---|---|---|
| Substitution | A→X, B→Y … | Permutation of the alphabet (a bijection on the set of letters). |
| Transposition | ABCDE → EDCBA | Rearranging the positions of letters (permutation of indices). |
| Affine | (f(x) = (ax + b) \bmod 26) | Linear mapping over the cyclic group (\mathbb{Z}_{26}). |
| Binary/Unary | A→0, B→01, C→010 | Encoding as variable‑length binary strings (prefix‑free codes). |
| Block | AB → 01, CD → 10 … | Mapping of blocks (length > 1) to codes. |
| Run‑length | AAAAA → 5A | Counting consecutive identical symbols. |
3. Mathematical Foundations
3.1 Permutation Groups
A substitution cipher is a permutation (\pi) on the set of letters.
Properties:
- Order: the smallest (k) such that (\pi^k = \text{id}).
- Cycle decomposition: e.g., (\pi = (A;B;C)(D;E)).
- Parity: even vs. odd permutations (determinant of the permutation matrix).
Why it matters
If two coded strings share a permutation, we can deduce the mapping by aligning the cycles.
3.2 Linear Algebra & Affine Ciphers
Treat letters as numbers (0–25).
An affine cipher: (f(x) = (a x + b) \bmod 26).
- Condition for invertibility: (a) must be coprime with 26 (i.e., (\gcd(a, 26)=1)).
- Inverse: (f^{-1}(y) = a^{-1}(y - b) \bmod 26).
- Matrix form: (\begin{bmatrix} a & b \ 0 & 1 \end{bmatrix}) acting on (\begin{bmatrix} x \ 1 \end{bmatrix}).
3.3 Prefix‑Free Codes & Information Theory
When codes are variable length (e.g., binary strings), the code must be prefix‑free so that the decoding is unambiguous.
- Kraft’s inequality: (\sum_{i} 2^{-l_i} \le 1).
- Huffman coding: optimal prefix‑free binary code for a given symbol frequency distribution.
3.4 Matrix Representation of Transpositions
Let (M) be a permutation matrix of size (n \times n).
For a word (w = w_1 w_2 … w_n) represented as a column vector, the transposed code is (M w).
Decoding multiplies by (M^{-1}) (which equals (M^T) for permutation matrices).
4. Analytical Techniques
| Situation | Strategy | Example |
|---|---|---|
| Only one example pair given | Assume bijection; deduce mapping for all letters that appear. | A→01, B→10 → decode 10 → B. |
| Multiple example pairs | Cross‑check consistency. If |