Questions tagged [encoding-scheme]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
26
votes
4answers
18k views

Is Morse Code binary, ternary or quinary?

I am reading the book: "Code: The Hidden Language of Computer Hardware and Software" and in Chapter 2 author says: Morse code is said to be a binary (literally meaning two by two) code because ...
20
votes
3answers
4k views

Why is this code uniquely decodable?

Source alphabet: $\{a, b, c, d, e, f\}$ Code alphabet: $\{0, 1\}$ $a\colon 0101$ $b\colon 1001$ $c\colon 10$ $d\colon 000$ $e\colon 11$ $f\colon 100$ I thought that for a code to be uniquely ...
17
votes
4answers
5k views

Huffman encoding: why is there no need for a separator?

...
13
votes
1answer
228 views

How do I find the shortest representation for a subset of a powerset?

I'm looking for an efficient algorithm for the following problem or a proof of NP-hardness. Let $\Sigma$ be a set and $A\subseteq\mathcal{P}(\Sigma)$ a set of subsets of $\Sigma$. Find a sequence $w\...
9
votes
2answers
2k views

Does a binary code with length 6, size 32 and distance 2 exist?

The problem is to prove or disprove the existence of $C$, s.t., $|c| = 6,\forall c\in C$; $|C| = 32$; $d(c_i,c_j)\geq2,1\leq i<j\leq32$. ($d$ stands for hamming distance) I tried to construct a ...
8
votes
1answer
263 views

Understanding compression/encoding in linear time

I'm reading the paper N. J. Larsson, A. Moffat: Offline Dictionary-Based Compression, which describes a compression algorithm that, if I understand it correctly, is quite similar to Byte pair encoding....
6
votes
1answer
426 views

Optional prefix code for the naturals

The naturals $\mathbb{N}$ can be encoded with a binary unary code such as $$ \begin{align} 1&=0_b\\ 2&=10_b\\ 3&=110_b\\ &... \end{align} $$ The length this the ...
6
votes
2answers
172 views

Can nested structures be encoded more “readably” with a single delimiter?

Imagine you have two systems of delimiting. One with paired delimiters, [ and ]: [abc] ...
6
votes
1answer
171 views

Error correcting permutation code

Let's say you have $n$ symbols. You can encode a $\log_2(n!)$-bit message by permutating the symbols. I will call this a permutation code (if you have seen this concept before, I would love to see a ...
5
votes
3answers
213 views

Defining computable functions on arbitrary sets

Turing machines take inputs that are strings of symbols from some alphabet, and they give outputs that are strings of symbols from the same alphabet. To show that a function is computable, we have to ...
5
votes
1answer
293 views

How to find a basis which is guaranteed to need 9 or less characters to represent a 12 digits number?

I'm trying to map a 12 digit number into a fixed width file. For a number of reasons, it must be compressed in such a way that it is guaranteed to be less than or equal to 9 characters (alpha numeric ...
5
votes
2answers
6k views

What is an “encoding” of a TM?

I'm currently working on a reduction from $A_{TM}$ to another language, and have been reading through some example proofs. I've come across the situation where, for example, we have $L = \{ \langle M,...
5
votes
1answer
162 views

Prefix encoding of algebraic data types

I'm new to coding theory and formal proofs, and am struggling to understand how to construct and reason about prefix-free encoding algorithms on algebraic data types. I hope it's clear if I use ...
5
votes
1answer
337 views

What is the minimum required storage for a sparse, depth-first octree?

For a numerical simulation framework, I use a hierarchical Cartesian grid in 3D to discretize the computational domain. I am thus looking for the most space-efficient way to store the resulting octree ...
5
votes
0answers
62 views

Name of a type of code similar to block codes

I've encountered a system where I need to construct a sort of quasi block code: We want to encode a symbol $s$ from a finite-sized alphabet $\mathcal{S}$ using $N$ segments of information. The $i^{...
4
votes
2answers
793 views

How does one choose an optimal alphabet for finding a Huffman encoding?

Huffman encoding will perform best when the distribution of symbols of an alphabet that the string to be encoded uses is dyadic. Given an arbitrary bit string S, ...
4
votes
1answer
4k views

A string representation of any Turing machine

The set of all Turing machines is said to be countable. The central idea of the proof of this fact is that every Turing machine can be written as a finite string of characters. I am having trouble ...
4
votes
1answer
573 views

Can I encode a graph in a unary alphabet

For a graph $G=(V,E)$, I build an adjacency matrix and encode it into binary, clearly. Now, imagine the alphabet I am given is $\Sigma=\{1\}$, is there a way for me to encode any graph instance with ...
4
votes
3answers
6k views

What are two's complement integers?

Can someone explain in plain English what "two's complement integer" means? I read this: in Java long is a 64-bit signed two's complement integer
4
votes
2answers
152 views

Succinct bounded-sum array with $O(1)$ access

Assume we have a $n$ sized integer array $A$, and that we know that $\sum_{i\in[n]}A[i] \le M$. Assume we are using the RAM model with $\Theta(\log n)$ sized memory words (which can be read / written ...
4
votes
1answer
872 views

Designing a prefix code for integers?

trying to figure out how to approach this problem. Suppose a sender in a network wanted to communicate the length n of the block it will be using in a subsequent transmission. If there were not ...
4
votes
1answer
22 views

Compactly representing integers when allowed a multiplicative error

Consider the problem of representing in memory numbers in the range $\{1,\ldots,n\}$. Obviously, exact representation of such number requires $\lceil\log_2(n)\rceil$ bits. In contrast, assume we are ...
3
votes
3answers
994 views

Reconstructing files from binary

Popular view tells us that any kind of information is just a collection of bits, that is zeroes and ones placed in a particular order. I was thus having this thought. Suppose that I have some kind of ...
3
votes
1answer
321 views

Polynomially related lengths under two different encodings

I'm reading through "Computers and Intractability: A guide to the Theory of NP-Completeness" by Michael R. Garey and David S. Johnson, p. 20 and I came across this ...
3
votes
2answers
24 views

How to show that in noiseless coding theorem, the bound $\mathrm{MinACL}<H(P)+1$ is tight?

The theorem states that $$ H(P)\leq\mathrm{MinACL}(P)<H(P)+1 $$ where, $\mathrm{MinACL}$ means the minimum average code word length of a given information source, i.e. the average code word ...
3
votes
1answer
4k views

When would the worst case for Huffman coding occur?

I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the ...
3
votes
1answer
72 views

How many independent yes/no questions can be asked about a point in binary space (linear vs nonlinear codes)?

This question springs from thinking about the potential benefits of using nonlinear codes instead of linear codes. Say we have a point $x \in \{0,1\}^k$ and we want to guess what it is. A naive scheme ...
3
votes
1answer
851 views

Turing machine working only with 1's and blanks - how to encode input?

Let's say we have a Turing machine which head can only write 1 or blank to the tape (although it can read all symbols from any input alphabet correctly). Can we operate with it on any input? My ...
3
votes
2answers
320 views

Variable Length Encoding of Integers Using a Modulus Algorithm

Continuing on the theme from my last question Variable Length Encoding of Integers, I have come up with a simple encoding scheme, but for which an efficient algorithm eludes me. The constraints are ...
3
votes
1answer
38 views

Lexicographical position of a string in its type class

I have the following problem: Given a string $x\in\{1,...,M\}^+$ of length $n$. Let $S$ be the set of all words with exactly the same numbers of occurences of smybols as in $x$. In fact, $S$ consists ...
3
votes
1answer
434 views

Encoding algorithms better than or equivalent to Run Length Encoding

I have a table in which some values are repeated often as shown in the figure below. I want to encode that table such that it makes use of less memory. I have heard about run length encoding (RLE) but ...
2
votes
3answers
162 views

Integer linear programming formulation of formula in DNF

I have multiple sets, e.g., $$\{1, 2\}, \{2, 3, 4\}, \{1, 4\}$$ Each variable $1, 2, 3, 4$ is binary. I need to represent the following condition without additional variables $$(1 \land 2) \lor (2 \...
2
votes
2answers
63 views

Unique representation of 5-number sets with values 1-13

From a simulation I get 5 numbers 1-13. The nature of the simulation is that I do not get the numbers ordered. The value/rank of the the tuple is not order dependent 5 5 5 2 2 = 2 5 2 5 5. Values ...
2
votes
3answers
369 views

Is there any practical trick to mentally count in Gray code?

When I was fairly young, I taught myself to count in binary. I thought it would be a fun party trick to impress people. I soon found out that it was not. Over the years I've come to appreciate Gray ...
2
votes
2answers
2k views

Is there a difference between pure binary and binary?

In some books and on the internet I occasionally find "pure binary" and "binary" on its own, is there a difference between these two terms? If so, can someone describe briefly what they are?
2
votes
1answer
360 views

integer = c lg n (inputs of size n, Cormen 3rd, page 23)?

I just started with my "Algorithms" course. But my CS-background is lower than that of an average CS-student (I'm a data science student). Only had intro-2-prog course (Python/Java), that's it. ...
2
votes
1answer
33 views

Most Efficient Way to Map Generic Input To Generic Output

Lookup tables are one way to map x values to f(x) values. This lets you do computation in advance, and can give a low cost (performance wise) answer to complex calculations when they are needed in ...
2
votes
1answer
34 views

Viewing images that compressed using lossless algorithms

I am just trying to understand a few minor details regarding images that are compressed with lossless algorithms such as RLE. If a bmp image is compressed using RLE, when does the decompression ...
2
votes
1answer
137 views

Typical set in Shannon's source coding theorem

I was following the textbook by David Mackay: Information theory inference and learning algorithms. I have question on asymptotic equiparition' principle: For an ensemble of $N$ $i.i.d$ random ...
2
votes
1answer
78 views

Source Coding Theorem: what happen when go below N⋅H(x) bits?

I was following the text book by David Mackay: information theory inference and learning algorithms, this could be found online on his website. I have question on the source coding theorem (emphasis ...
2
votes
1answer
20 views

Prove that the upper bound in the Noiseless-coding theorem is strict

Given a probability distribution $p$ across an alphabet, we define redundancy as: Expected Length of codewords - entropy of p = $\ E(S) - h(p)$ Prove that for each $\epsilon$ with $0 \le \epsilon \...
2
votes
1answer
38 views

Methods, Routines, or Algorithms To Optimize Selection of String Compression Methods

When encoding a a 2D Datamatrix barcode, I want the smallest output size. There are means to encode a compressed a string using some methods like C40. Reference: Here's a reference: https://en....
2
votes
1answer
134 views

How to uniquely encode a vector of non-increasing positive integers

Given a vector of positive integers $A=[a_1, \cdots, a_n]$, where $\sum_{1 \leq i \leq n}a_i = n(n-1)$ and $a_i \geq a_j$ iff $i \geq j$, I am interested in encoding the vector, maintaining the ...
2
votes
2answers
342 views

How much bits need to add to 100bit of data in order to correct up to 10bits?

I'm trying to calculate how much minimum bits need to be added to data of 100bits, in order to correct 10 bits that are messed up by: bits that deleted (Erasure Correcting) bits that corrupted (Error ...
2
votes
0answers
18 views

How can I optimise a 8b10b encoding for maximum alignment?

Imagine you encode an 8 bit symbol as a 10 bit symbol that is sent sequentially over a wire. The goal at the receiver is to detect the byte boundary. Since there are 4 times more encoded symbols than ...
2
votes
0answers
36 views

Card Shuffling, Bounding Mixing time using Paths and Flows

I've been struggling with a problem that is very similar to a 2014 question posted here. The question in particular is 3(1) and 3(2). To paraphrase, we are supposed to use paths and an encoding ...
2
votes
0answers
61 views

Error detection code supporting arithmetic

I am looking for error detection codes, which support addition in the encoded domain and are separate (a tuple of ($N$, $R(N)$), where $N$ denotes the functional value and $R(N)$ its redundancy). So ...
2
votes
0answers
49 views

Typed representation of a memory model

Assume a simple procedural language, where statements write and read from local memory via references and procedures accept arguments of n different scalar types (say floats, ints and strings) and ...
1
vote
1answer
262 views

Why encoding of graph in adjacency matrix is $\Omega (\sqrt n)$?

in the textbook of CLRS, p.1062 he says the following: if we use "reasonable" encoding of a graph as its adjacency matrix, the number m of vertices in the graph is $\Omega (\sqrt n)$, where n = |$\...
1
vote
2answers
77 views

Unary encoded language set

While reading the book theory of computation by Michael Sipser, I did not understand the language given below. I will explain the problem first $$L = \{1^n :n \in \mathbb{Z}\}$$ Where $\mathbb{Z}...