gammakódolást

Gamma encoding, also known as gamma coding or Elias gamma coding, is a universal code used for encoding positive integers. It is a form of prefix coding, meaning that no codeword is a prefix of another codeword, which allows for unambiguous decoding. The encoding process is based on the binary representation of the number to be encoded.

To encode a positive integer $N$, the first step is to represent $N$ in binary. Let the binary representation of $N$ have $L$ bits, where the most significant bit is 1. Then, the gamma code for $N$ consists of $L-1$ zeros followed by the $L$-bit binary representation of $N$. For example, the number 5 is represented in binary as 101. This representation has $L=3$ bits. Therefore, the gamma code for 5 consists of $L-1=2$ zeros followed by the binary representation 101, resulting in the codeword 00101. The number 1, in binary 1, has $L=1$ bit, so its gamma code is $1-1=0$ zeros followed by 1, which is just 1.

Gamma encoding is efficient for numbers that are close to powers of two. The length of the gamma code for an integer $N$ is approximately $2 \log_2 N$. It is a type of variable-length code, where smaller numbers are represented by shorter codewords. This property makes it suitable for applications where the distribution of numbers tends to be skewed towards smaller values, such as in data compression and certain communication protocols. Elias gamma coding is a specific implementation of this concept.