Coding-decoding

Coding‑Decoding – Advanced Study Notes

(For the Jammu & Kashmir Patwari / Lekhpal Reasoning Ability program – MIT‑level treatment)

1. Introduction

Coding‑decoding is the process of transforming a sequence of symbols (the plaintext) into another sequence (the ciphertext) and, given the ciphertext together with some knowledge (the key or the decoding rule), recovering the original plaintext.

In reasoning‑ability exams, coding‑decoding problems test your ability to:

| • | Recognise patterns |
| • | Infer hidden rules |
| • | Deduce the key from limited data |
| • | Apply mathematical reasoning to reconstruct the mapping |

The following notes build a rigorous foundation, starting from set‑theoretic principles and ending with a challenging problem that blends combinatorics and error‑correcting codes.

2. First Principles

2.1 Sets, Functions, and Bijections

• Alphabet
  (\mathcal{A}={a_1,a_2,\dots,a_m}) – finite set of symbols.
• Strings
  (\mathcal{A}^*=\bigcup_{k\ge0}\mathcal{A}^k) – all finite strings over (\mathcal{A}).
• Coding function
  (C:\mathcal{A}^\to\mathcal{A}^).
• Decoding function
  (D:\mathcal{A}^\to\mathcal{A}^).

Property 1.
(C) must be injective (no two different strings map to the same ciphertext) for decoding to be possible.
Property 2.
If (C) is injective, its inverse (C^{-1}) exists on (\operatorname{im}(C)), giving the unique decoding rule (D=C^{-1}).

Proof Sketch
Assume (C(x)=C(y)) with (x\neq y). Then (D) would have to satisfy (D(C(x))=x) and (D(C(y))=y) simultaneously, impossible if (C(x)=C(y)). ∎

Thus every decodable coding scheme is a bijection on its domain.

2.2 Group Action on Alphabets

Many classical ciphers are built from group actions.

• Substitution ciphers arise from the symmetric group (S_m) acting on (\mathcal{A}).
• Affine ciphers use the group of affine transformations ({x\mapsto ax+b\mid a,b\in\mathbb{Z}_m,,\gcd(a,m)=1}).

In all cases, the key is an element of the group, and decoding is applying the inverse group element.

3. Formal Foundations

3.1 Algebraic Modelling

Let the alphabet be (\mathbb{Z}_m={0,1,\dots,m-1}).
A linear coding rule can be written as:

[ C(x)=Ax+B \pmod m ]

where (x\in\mathbb{Z}_m^n) is the vector of plaintext symbols, (A) an (n\times n) invertible matrix over (\mathbb{Z}_m), and (B) a translation vector.

Why linearity matters:

• Decoding is simply (x = A^{-1}(C(x)-B)).
• The invertibility of (A) (determinant coprime to (m)) guarantees a bijection.

3.2 Finite Automata Perspective

A finite state machine (FSM) can implement a coding rule that depends on context (e.g., previous symbols).

• Transducer (T=(Q,\Sigma,\Delta,\delta,\lambda,q_0))
  • (Q) – finite set of states
  • (\Sigma) – input alphabet
  • (\Delta) – output alphabet
  • (\delta:Q\times\Sigma\to Q) – transition
  • (\lambda:Q\times\Sigma\to\Delta^*) – output function

Coding is the mapping (C(x)=\lambda^*(q_0,x)).
Decoding requires an inverse transducer, which might not exist if the transducer is not right‑invertible.

4. Classical Cipher Families