Questions tagged [encoding-scheme]
The encoding-scheme tag has no usage guidance.
136
questions
1
vote
1
answer
41
views
How to formally show computational equivalence or universality using encodings?
I want to formally show that a computational system $\mathcal M$ is computationally universal by showing it is computationally equivalent to some already known universal system, i.e. some UTM.
To show ...
- 11
0
votes
0
answers
39
views
Calculation of compression ratio using arithmetic encoding?
Arithmetic encoding is one of the most famous entropy encoding techniques, and I am using it to encode an image.
For this, I am using the built-in function of Matlab that also gives other values such ...
1
vote
0
answers
60
views
Initialization of embedding space value for VQ-VAE
I am trying to study a research paper about VQ-VAE: Neural Discrete Representation Learning, Aaron van den Oord, Oriol Vinyals, Koray Kavukcuoglu, NeurIPS 2017.
I have difficulty to understand the ...
- 123
-1
votes
2
answers
61
views
What is the minimum number of bytes required to store the sum of two primitive integers?
Motivation
An informal way word this question is,
How would re-do some of the weird promotion rules in languages descended from C, like C# or Java. The goal would as to minimize human bewilderment ...
0
votes
1
answer
56
views
ASCII invariant string for base64 Encoding
I know the basics about base64 encoding, but thinking about it abstractly I have a theoretical question.
If we consider base64 a mathematical function(in our case computable), Does there exists an ...
- 153
1
vote
2
answers
35
views
An Arithmetic Encoding's length being ambiguous?
Say they are two tokens, A and B. A has probability weight 0.99 (and B has 0.01). If I want to encode the sequence "AAA", wouldn't the binary encoding just be "0"? And wouldn't ...
- 532
-1
votes
1
answer
52
views
Correct way to encode strings
I'm interested in analyzing the randomness of strings using relative count for 1-, 2-, etc tuples.
E.g. for a long string "abbccba.." with an alphabet <...
- 111
0
votes
2
answers
162
views
File conversion to binary format to save storage space
Our test log files are stored in .asc format. Each file contains around 5000 rows of these Logging Strings as shown in the image. I would like to reduce the size of these files.They are around 4-5 MBs ...
1
vote
1
answer
50
views
Are there adaptive algorithms/data structures for sparse and non sparse vectors?
A sparse 1D array of integers is commonly encoded as pairs of [index, value], which consumes 2 memory spots per value.
A dense 1D array is commonly encoded as a linear array of values [value1, value2, ...
- 131
1
vote
1
answer
350
views
Hash / Compression algorithm to shorten text?
I desperately need a hash / compression function that is suited to shorten text.
The context is this: I want to bring order and sort my box with hundreds of charging adapters (duh). After I determined ...
- 31
1
vote
1
answer
43
views
fpaq0.cpp is supposedly a "0-order" compressor. Why does it use a context then?
In http://mattmahoney.net/dc/dce.html#Section_32 Matt Mahoney states:
The simplest of these is the order 0 coder fpaq0.
in http://mattmahoney.net/dc/dce.html#...
- 21
1
vote
4
answers
1k
views
What is the name of the following binary encoding?
S is a the set of binary strings in Shortlex order: [0,1,00,01,10,11,...]
I want to encode / decode natural numbers with the following scheme:
Encoding N: For ...
- 299
1
vote
3
answers
403
views
How bits translated into text on the screen?
recently i started studying computer science and computer graphics, and one question really haunts me. Mby someone can explain this. How bit patterns become translated into (for example ) text. I know ...
0
votes
1
answer
28
views
Probability of certain symbols in a mapping of symbol and code word
Let's say you have this mapping of symbols and codewords:
$$
\begin{array}{cc}
\hline \text { Symbol } & \text { Codeword } \\
\hline \text { A } & 101 \\
\text { B } & 100 \\
\text { C } &...
- 125
0
votes
4
answers
160
views
Why does the BOM consist of two bytes instead of one for example in encoding utf-16
Why does the BOM consist of two bytes instead of one for example in encoding utf-16?
Information about the order of bytes can be easily saved on just one byte.
Is it because it would be good for the ...
- 111
3
votes
1
answer
105
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 ...
- 133
2
votes
1
answer
223
views
How does strong NP-completeness agree with encoding complexity?
I've recently read about the concepts of weak and strong NP-completeness, but faced a problem in wrapping my head around them. I've understood that problems which have numerical parameters (like ...
- 161
2
votes
4
answers
165
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 ...
- 23
1
vote
2
answers
33
views
Error correction for windowed reads from cyclic tapes
I have an array of N symbols written on a cyclic tape. I read a sequence of M symbols starting from a random place on the tape. What error correcting scheme and even a coding scheme should I use for ...
- 155
1
vote
1
answer
49
views
A question about domains in Karp reductions
A basic question or request for clarification regarding Karp reducibility:
Let $\Sigma^*$ be the set of all finite strings of 0's and 1's. Call a subset of $\Sigma^*$ a language. Let $\Pi$ denote ...
- 319
0
votes
0
answers
142
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)$,...
- 246
1
vote
2
answers
208
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 ...
- 133
1
vote
0
answers
55
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}$ ...
- 21
2
votes
0
answers
39
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 ...
- 21
2
votes
1
answer
73
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]...
- 153
2
votes
1
answer
60
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 ...
- 199
1
vote
2
answers
48
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 ...
- 2,163
2
votes
1
answer
142
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 ...
- 23
45
votes
9
answers
9k
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 ...
- 459
0
votes
0
answers
154
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 ...
- 952
2
votes
1
answer
100
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 ...
- 199
0
votes
1
answer
340
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 ...
- 199
2
votes
1
answer
840
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: ...
user121977
2
votes
2
answers
47
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 ...
2
votes
1
answer
51
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 ...
- 213
0
votes
1
answer
147
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 ...
- 461
2
votes
0
answers
77
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?
- 33
2
votes
3
answers
302
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 ...
- 150
1
vote
2
answers
202
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 ...
- 291
-2
votes
1
answer
111
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 ...
- 3
0
votes
3
answers
1k
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
1
answer
51
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 ...
- 291
1
vote
1
answer
47
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 ...
- 121
1
vote
1
answer
69
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, ...
- 143
1
vote
1
answer
92
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 ...
- 952
2
votes
1
answer
191
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$ ...
- 55
2
votes
1
answer
472
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.
- 55
1
vote
0
answers
124
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 ...
- 111
2
votes
1
answer
33
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 \...
- 38
1
vote
0
answers
83
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 "...
- 333