Coding-decoding

Verbal Reasoning · free study notes

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

  1. Injective → no two letters map to the same code.
  2. Surjective → every code in (C) corresponds to some letter in (S).
  3. 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

Your note

Page 1

Doubt hai is topic me?

Free AI teacher se poocho — 24/7, step by step.