Questions tagged [encoding-scheme]
The encoding-scheme tag has no usage guidance.
121
questions
2
votes
1answer
33 views
Optimal encoding scheme for semi-rewritable memory?
Let's define a "semi-rewritable" memory device as having the following properties:
The initial blank media is initialised with all zeroes.
When writing to the media, individual zeroes can ...
0
votes
0answers
33 views
Epsilon balanced Code
A linear code is termed as an $\epsilon -$balanced code if all the codewords are having fractional hamming weight $\in (1/2-\epsilon,1/2+\epsilon)$. I want to show that for every $\epsilon\in (0,1/2)$,...
2
votes
3answers
112 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 ...
1
vote
2answers
116 views
What does an admissible numbering of computable functions look like?
I'm trying to understand how we can construct an admissible ordering of the computable (meaning, partial recursive) functions.
Initially my take on such an enumeration was from the point of view of an ...
1
vote
0answers
40 views
How do I compress data vectors in broadcast messages?
Let us model a wireless broadcast network as an undirected graph $G(V,E)$ where there is an edge between every pair of nodes ${i,j}\in V$ if they are in transmission range of each other. $w_{i\to j}$ ...
2
votes
0answers
17 views
Messy Representation Encoding example
I am currently working through Metaheuristics by El-Ghazali Talbi where he discusses encodings of algorithms.
"Messy representations: In linear representations of fixed length, the semantics
of ...
0
votes
0answers
19 views
Radix Economy of Complex Bases
If we extend the allowed bases for a numerical system to the complex numbers, is e still the most economic base? If not, what would it be?
There's the well-known formula for radix economy:
Where b is ...
1
vote
0answers
14 views
Encoding a lot of categorical variables
I have 10 million categorical variables (each variable has 3 categories). What is the best way to encode these 10 million variables to train a deep learning model on them? (If I use one hot encoding, ...
2
votes
1answer
59 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]...
2
votes
1answer
22 views
Intuitive explanation on why stochastic encoding performs better in channel coding
I am a little confused about stochastic encoding in channel coding. For example, in the identification problem (R. Ahlswede and G. Dueck, “Identification via channels”), the authors claim that we can ...
7
votes
3answers
490 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 ...
0
votes
0answers
14 views
Encoding a arbitrary stack trace into a fixed length value
Background
I would like to store the nodes of a Calling Context Tree using in a key value store. I need to be able to directly access a node by it's method name and complete stack trace. In addition ...
1
vote
2answers
33 views
Is there a way to store an arbitrarily big BigInt in a bit sequence, only later to convert it into a standard BigInt structure?
I am trying to imagine a way of encoding a BigInt into a bit stream, so that it is literally just a sequence of bits. Then upon decoding this bit stream, you would generate the standard BigInt sort of ...
43
votes
9answers
7k 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 ...
2
votes
1answer
38 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 ...
1
vote
2answers
119 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
0answers
32 views
CNF encoding of additions
I have $m$ equations of the following form:
$$x_1+x_2+\cdots+x_n=s,$$
where each variable is either 1 or 0, and the total number of variables is $m\approx3{,}000$. So I’m thinking of modeling each ...
2
votes
1answer
46 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 ...
0
votes
1answer
43 views
Are all prefix codes uniquely decodable?
I can't think of any counterexample but I can't find any such statement on the internet or my textbook either. I know that for each uniquely decodable code, there exists a prefix code with the same ...
1
vote
1answer
88 views
How to enumerate all Turing machines?
Why is this true: “There are countably many Turing Machines”
In the top answer for this question a description of how to enumerate all Turing machines is given.
It all is clear except for one part: ...
1
vote
1answer
24 views
Worked out example of Slepian-Wolf Theorem
Note: First posted this on Theoretical Computer Science Stack Exchange, but deleted it from there since it seems to be off-topic.
The Slepian-Wolf theorem states that sequences of outputs from two ...
1
vote
0answers
18 views
Mathematics of the upper bound for the encoded input of an instance Kruskal's MWST problem
I was going through the classic text "Introduction to Automata Theory, Languages, and Computation" by Hofcroft, Ullman and Motwani where I came across the encoding of an instance of Kruskal's Mininum ...
0
votes
1answer
42 views
Help in understanding 'reasonable' encoding of inputs
I read that a reasonable encoding of inputs is one where the length of the encoding is no more than a polynomial of the 'natural representation' of the input. For instance, binary encodings are ...
2
votes
0answers
50 views
What is “orthogonality” in the context of Instruction Encoding?
What does it mean by "orthogonality" in the context of Instruction Encoding?
Why CISC Architecture is orthogonal while RISC is not?
1
vote
2answers
68 views
Data Compression :Compress a Compressed File
Suppose we have file A that has been compressed by the the method B and the output-file is C, now if I am not wrong We can not compress C more by method B, but there might another method=algorithm D ...
-2
votes
1answer
74 views
Lambda Expression Reduction
I am unable to solve the following lambda expression using both normal order (Call-by-name) and applicative order (Call-by-value) reduction. I keep getting different answers for both. This is the ...
0
votes
3answers
581 views
Why the 127 encodings of ASCII needed to be extended to 256?
As you all know the ASCII chart needed to be extended from 127 encoding to 256, I can't really see why. Some google expert on Coursera said "We needed that because of the foreign languages".
I still ...
1
vote
1answer
31 views
Encoding System that Assign Same Number of Bits for Each Character
I am trying to get a binary string that has been converted from text of a text file, I am able to get that but the problem is, I need each character to be represented by same number of bits, but that ...
1
vote
1answer
39 views
What is the difference between rateless and online encoding?
Definitions of Rateless encoding and Online encoding are as follows.
Error-correcting codes that employ no fixed block length are called rateless or fountain codes.
Online encoding refers to the ...
0
votes
1answer
54 views
Prove that in an optimal code, if the letter frequencies are increasing, the encoding lengths are monotonically decreasing
I am trying to prove that, in an optimal encoding (possibly Huffman?), if letter frequencies are increasing, their encoding lengths are monotonically decreasing. It is intuitive that this makes sense, ...
1
vote
1answer
60 views
Encoding order relations in CNF
I want convert timetable scheduling problems to SAT problems. Suppose there are $t$ time slots and $c$ classes. I will define $t\times c$ variables $x_{ij}$, which is true iff class $j$ takes place in ...
2
votes
1answer
33 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$ ...
2
votes
1answer
58 views
Determining key from plaintext and ciphertext (Vigenère)
I was wondering why mathematically we can know the key in the Vigenère cipher if we know in advance a message and its encryption.
1
vote
0answers
34 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
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?
2
votes
2answers
529 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
3answers
296 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
1k 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
27 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
34 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 "...
21
votes
3answers
5k 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
25 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
48 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
29 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
2answers
128 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
222 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
41 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
45 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
104 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 ...
