2022 Developer Survey is open! Take survey.

Questions tagged [encoding-scheme]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
45 votes
9 answers
8k views

Is UTF-8 the final character encoding for all future time?

It seems to me that Unicode is the "final" character encoding. I cannot imagine anything else replacing it at this point. I'm frankly confused about why UTF-16 and UTF-32 etc. exist at all, not to ...
user avatar
  • 459
30 votes
4 answers
28k 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 ...
user avatar
21 votes
3 answers
6k 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 ...
user avatar
18 votes
4 answers
6k views

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

...
user avatar
  • 291
13 votes
1 answer
272 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\...
user avatar
  • 626
9 votes
2 answers
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 ...
user avatar
  • 185
8 votes
1 answer
312 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....
user avatar
  • 219
7 votes
2 answers
12k 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,...
user avatar
7 votes
2 answers
1k 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, ...
user avatar
  • 317
7 votes
3 answers
650 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 ...
user avatar
6 votes
1 answer
628 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 ...
user avatar
  • 345
6 votes
2 answers
187 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] ...
user avatar
6 votes
1 answer
233 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 ...
user avatar
  • 756
5 votes
3 answers
353 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 ...
user avatar
  • 916
5 votes
1 answer
298 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 ...
user avatar
5 votes
1 answer
5k 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 ...
user avatar
5 votes
1 answer
212 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 ...
user avatar
  • 113
4 votes
4 answers
2k 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 ...
user avatar
  • 171
4 votes
3 answers
11k 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
user avatar
4 votes
1 answer
713 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 ...
user avatar
4 votes
2 answers
177 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 ...
user avatar
  • 2,584
4 votes
1 answer
1k 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 ...
user avatar
4 votes
1 answer
8k 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 ...
user avatar
4 votes
1 answer
33 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 ...
user avatar
  • 2,584
3 votes
3 answers
1k 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 ...
user avatar
  • 133
3 votes
4 answers
104 views

Is there a binary representation where the encoding distance grows with the arithmetic distance?

I need to binarily encode/decode small integers (around 10 bits), in such a way that the hamming distance of the encoded number grows monotonically with the (absolute value) arithmetic distance of the ...
user avatar
  • 33
3 votes
2 answers
54 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 ...
user avatar
  • 185
3 votes
1 answer
400 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 ...
user avatar
  • 3,570
3 votes
1 answer
82 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 ...
user avatar
3 votes
2 answers
676 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 ...
user avatar
  • 133
3 votes
1 answer
2k 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 ...
user avatar
  • 914
3 votes
2 answers
378 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 ...
user avatar
3 votes
1 answer
45 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 ...
user avatar
  • 984
3 votes
1 answer
70 views

What is the nature of the two bits of data held in a computer memory cell?

I hope this question doesn't offend anyone. I start off by saying that I have and always had difficulty understand the language used in computer science so I have to interpret everything into the ...
user avatar
  • 33
2 votes
3 answers
219 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 \...
user avatar
  • 175
2 votes
2 answers
81 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 ...
user avatar
  • 431
2 votes
1 answer
132 views

Period of sum of two periodic sequences

I was wondering, what is to be the shortest possible key using Vigenere encryption, if a text is ciphered one time with a key of length $i$ using Vigenere and second time with a key of length $j$ ...
user avatar
2 votes
1 answer
510 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 = |$\...
user avatar
  • 707
2 votes
2 answers
572 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 ...
user avatar
  • 351
2 votes
2 answers
3k 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?
user avatar
  • 123
2 votes
1 answer
60 views

Encoding two 6-bit positive integers compactly

Is it possible to encode two 6-bit wide positive integers a and b guaranteed to be in [0, 63]...
user avatar
2 votes
3 answers
199 views

Name of binary encoding scheme for integer numbers

I once found on Wikipedia a nice technique for encoding $k \in (2^{n-1}, 2^n)$ uniformly distributed integer numbers with less then $\log_2n$ average bits/symbol, thanks to a simple to compute ...
user avatar
2 votes
1 answer
91 views

Adaptive arithmetic coding confusion

I'm confused about the point of adaptive arithmetic coding. I understand that static arithmetic coding involves using preset probabilities of symbols that remain static during the whole process. I ...
user avatar
  • 23
2 votes
1 answer
56 views

Why is channel capacity of AWGN infinite?

My professor taught us that channel capacity of AWGN channel is infinite without any input power constraints. The noise is $Z \sim \mathcal{N}(0,\sigma^2) $. There is no constraint on input signal. I ...
user avatar
2 votes
2 answers
141 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}...
user avatar
  • 1,127
2 votes
1 answer
739 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. ...
user avatar
2 votes
1 answer
38 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 ...
user avatar
  • 1,320
2 votes
1 answer
36 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 ...
user avatar
2 votes
1 answer
176 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 ...
user avatar
  • 151
2 votes
1 answer
91 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 ...
user avatar
  • 151