# Questions tagged [encoding-scheme]

The tag has no usage guidance.

121 questions
Filter by
Sorted by
Tagged with
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 ...
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)$,...
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 ...
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 ...
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}$ ...
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 ...
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 ...
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, ...
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]...
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 ...
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 ...
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 ...
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 ...
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 ...
38 views

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 ...
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 ...
32 views

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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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$ ...
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.
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 ...
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?
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 ...
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 ...
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 ...
27 views

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 ...
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 ...
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 ...
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 ...