Questions tagged [encoding-scheme]
The encoding-scheme tag has no usage guidance.
91
questions
1
vote
0answers
13 views
Base-N encoding with smallest output
I have a set of bytes (utf-8), and need to encode them into the smallest dataset possible using a Base N encoding scheme. Is it simply the higher the Base N encoding is (ie something like Base85 ...
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?
0
votes
0answers
12 views
MDS codes with a given proportion of weights
I was trying to understand the hamming weight distribution of codewords in MDS codes.
I read (https://wiki.cse.buffalo.edu/cse545/content/mds-codes) the following:
Let C be a $[n, k, d]$ MDS code . ...
2
votes
2answers
452 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 ...
5
votes
1answer
353 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
3answers
236 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 ...
2
votes
3answers
500 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
1answer
21 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 \...
1
vote
0answers
23 views
Difference between a regular and a stationary source?
As far as I understand a stationary source is a regular source but it's not necessarily true the other way around.
And a stationary source is a source for which its distribution is unaffected by a "...
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 ...
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 ...
1
vote
1answer
15 views
Prove the MinAveCodeLen of a product information source is less than the sum of that of the multiplicand and multiplier source?
The product of 2 independent sources $(S_A,P_A)$ and $(S_B,P_B)$ is defined as
$$
(S,P)\text{ s.t. }S = \{s_As_B|s_A\in S_A,s_B\in B\}\text{ and }\ P(s_As_B) = P_A(s_A)\cdot P_B(s_B)\,\forall s_A\in ...
3
votes
2answers
30 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 ...
2
votes
0answers
21 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 ...
0
votes
1answer
39 views
What is the concept of “encoding” in NP-completeness
Hi I have been reading Ch 34(NP-Completeness) Section 34.1 of CLRS and I am confused why do we need to consider different encodings. Everything is represented as binary at the end so why consider ...
0
votes
2answers
63 views
How many bits representation of data on tape of Turing machine consumes
I am wondering how to represent signed number, vector, matrix on binary tape of Turing machine to consume the smallest possible amount of memory.
For signed number it is obvious: encode sign as a ...
0
votes
1answer
101 views
What is the most compact (space efficient) method of storing an array of distinct integers?
I have an array of distinct integers which I want to save in the most compact manner. I may have to do occasional lookups, deletions, and insertions in this array so the compression algorithm must ...
0
votes
1answer
35 views
How hexadecimal representation is more compact and intelligible for documentation?
My textbook says,
"Instead, it is far better to use a hexadecimal representation for documentation purposes. Whether or not a code represents a binary number, it can be treated as ...
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....
1
vote
1answer
95 views
How to compare the efficiency of two encoding schemes or hypothesis languages?
My question is pretty basic, I'm looking for a named method if you know one, but also proper terminology, further reading, and anything this reminds you of if you don't. (I'm new to this, don't have ...
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
64 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 ...
1
vote
1answer
294 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
1answer
231 views
$2^1 + 2^2 + \cdots + 2^8$ in binary
Maybe these are silly question. I know almost nothing about computer science, so please let me know in the comment section if I should edit anything or delete it.
Let's say I have a function that ...
6
votes
1answer
431 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
175 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]
...
1
vote
1answer
66 views
What is responsible for the 1-1 correspondence between characters and binary?
Could someone explain to me what component(s) are responsible for translating binary into ASCII/UNICODE? For example, is it an assembly program that sets up a 1-1 correspondence between characters and ...
0
votes
0answers
23 views
LDPC:How to detect total number of errors in a codeword using minimum distance?
Currently, i working with LDPC for FPGA implementation. I have formed H matrix of size 102X204 (N=204,K=102,M=102,R=0.5). Doubt in Error detection and correction for bigger matrix.
I know that code'...
0
votes
0answers
41 views
Implementing a decoding algorithm for directed figure codes
I have to implement algorithm, where definitions, input and output of program go as follows:
$Σ$ - finite, non-empty alphabet
A
translation
in
$Z^2$
by vector
$u
= (
u_x
, u_y
)
∈
Z^...
1
vote
1answer
107 views
Given a binary matrix, how to find the starting coordinates of a sub matrix?
Say, I have an image of bit depth 1 (i.e. binary matrix) and I cropped the image to form a smaller matrix. From the cropped matrix (of a reasonable size). I need to know the starting coordinates from ...
1
vote
1answer
101 views
Calculating the information density of an encoding system
How do I calculate the information density of an encoding system?
This question came up as I was reading several papers about encoding data in DNA (I think I have gone through just about every major ...
0
votes
1answer
202 views
How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions
How to encode a sequence of n non-decreasing integer of [0, ..., m] fulfilling the following conditions:
no or minimal redundancy
only use 1 integer variable or k independent integer variables with a ...
1
vote
1answer
103 views
What should be the way to design code for such a situation?
I have a graph as given below:
Let us assume one node as transmitter and another as receiver.
We need to transfer particles in every time slot constrained by maximum particles N and minimum 0. The ...
0
votes
0answers
31 views
algorithm for encoding segmentations in RGBA data
I'm trying to figure out a good way of encoding object segmentation data into a single RGBA image. I'd like to not only distinguish between classes, but also individuals within classes, and be able to ...
0
votes
2answers
799 views
Understanding the binary and hexadecimal representations of UTF-8
Here is a code point: U+091D. The symbol it represents in UTF-8 is झ. In hex the symbol requires three bytes: e0 a4 9d. But it ...
0
votes
1answer
111 views
Encode an ascii string in base 15
How can I encode an ascii string in base 15?
In other words, I have the following characters available:
0123456789abcde
I have no idea how to do this. What do ...
5
votes
1answer
165 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 ...
2
votes
3answers
165 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
65 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 ...
1
vote
2answers
82 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}...
2
votes
1answer
441 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
139 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 ...
0
votes
0answers
32 views
Error Detection Distance of Residue Codes
Given a residue code representing a number N with the tuple (N, R(N))where R(N) equals ...
4
votes
2answers
155 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 ...
8
votes
1answer
277 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
178 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 ...
1
vote
0answers
380 views
Encoding Turing machines in binary in a simple way that gurarentee unique readability
I may come across something like (let $X$ be a binary representation of a Turing machine $M$), I know that we can easily encode the description of the machine as sequence of numbers (by assigning a ...
2
votes
0answers
50 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
0answers
175 views
Number of unique prefixes in canonical huffman tree
I am trying to implement decompression algorithm based on huffman trees. I am trying to validate my assumptions.
Assume that you have alphabet of 350 symbols. Maximum encoded code length is 15 bits. ...
1
vote
0answers
80 views
Byte Stuffing, escaping a flag at maximum frame
I want to encode a message using byte stuffing where every frame delimited by a flag byte 'F' at both ends and escape code equal to the character E. I am trying to encode the message 'DEEP-FRIED-...
