# Questions tagged [encoding-scheme]

The tag has no usage guidance.

136 questions
Filter by
Sorted by
Tagged with
1 vote
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 ...
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
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 ...
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 ...
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 ...
1 vote
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 ...
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 <...
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
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, ...
1 vote
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 ...
1 vote
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#...
1 vote
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 ...
1 vote
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 ...
28 views

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 ...
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 ...
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: ... 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 ...
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 ...
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 ...
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?
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 ...
1 vote
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 ...
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 ...
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
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 ...
1 vote
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 ...
1 vote
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, ...
1 vote
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 ...
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$ ...
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.
1 vote
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 ...
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 \...