Skip to main content

Questions tagged [coding-theory]

The challenge involves the topic of encoding and coding theory, as in error correction and compression. (Not to be confused with program source code).

Filter by
Sorted by
Tagged with
16 votes
5 answers

Prefix code generator

In this challenge, we consider an encoding from positive integers (up to a limit) to binary sequences. Some examples: ...
Bubbler's user avatar
  • 76.9k
15 votes
10 answers

Gray code on N symbols

A Gray code is a permutation on binary numbers where incrementing or decrementing a number only ever causes a single bit to change. For example, a Gray code for the binary numbers up to 7 (so, with 3 ...
pxeger's user avatar
  • 23.9k
22 votes
21 answers

Fibonacci Encoding

Fibonacci coding is a universal code, which can encode positive integers of any size in an unambiguous stream of bits. To encode an integer \$ n \$: Find the largest Fibonacci number less than or ...
pxeger's user avatar
  • 23.9k
27 votes
11 answers

Test if a Gray code is Beckett

Background An \$n\$-bit Gray code is an ordering of \$2^n\$ binary sequences so that adjacent sequences always differ by exactly one bit. A Beckett-Gray code is a special kind of Gray code. In ...
Bubbler's user avatar
  • 76.9k
8 votes
3 answers

Generate Hamming codes

Given a stream of bits, output the shortest possible Hamming code that encodes it. The steps to generate the Hamming code are as follows, although your submission does not necessarily have to conform ...
Doorknob's user avatar
  • 71.5k
41 votes
14 answers

Incrementing Gray Codes

Introduction A Gray Code is an alternative to binary representation in which a number is incremented by toggling only one bit, rather than a variable amount of bits. Here are some gray codes along ...
Patrick Roberts's user avatar
7 votes
6 answers

Generate m-sequences

Introduction Maximum-length sequences, usually known as m-sequences, are binary sequences with some interesting properties (pseudo-noise appeareance, optimal periodic autocorrelation) which make them ...
Luis Mendo's user avatar
  • 105k
13 votes
7 answers

Code the Huffman!

Or else he will huff and puff and blow your house down! That was completely irrelevant. This challenge is actually about Huffman coding. The gist of it is the frequency of characters in a given text ...
El'endia Starman's user avatar
12 votes
1 answer

An optimization version of the Hadamard problem

First, some definitions. A Hadamard matrix is a square matrix whose entries are either +1 or −1 and whose rows are mutually orthogonal. The Hadamard conjecture proposes that a Hadamard matrix of ...
user avatar
6 votes
1 answer

The Gray area of n-ary codes

Write a program or function that takes a base n and a number x, and returns or outputs the n-...
matsjoyce's user avatar
  • 1,339
21 votes
8 answers

Correct errors using Hamming(7,4)

The Hamming(7,4) code goes back to 1950. Back then Richard Hamming worked as a mathematician at Bell Labs. Every Friday Hamming set the calculating machines to perform a series of calculation, and ...
Jakube's user avatar
  • 21.9k