Questions tagged [encoding-scheme]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
2answers
104 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
37 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
14 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 ...
-1
votes
0answers
26 views

How should I decode the string?

I am working in an data entry application and it saves the data in a .db file with some sort of encoding. It has columns startdate, enddate, starttime, endtime, f1, f2 upto f15 and each column stores ...
0
votes
0answers
18 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 ...
0
votes
0answers
12 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
58 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 ...
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
32 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
votes
1answer
32 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 ...
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 ...
0
votes
0answers
27 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
44 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
30 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
76 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: ...
2
votes
1answer
31 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 ...
1
vote
1answer
21 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
17 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
35 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
48 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
71 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
65 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
73 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
575 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
29 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
37 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, ...
0
votes
0answers
21 views

How to model most optimized encoding of string data

Sorry if this question isn't super well defined, I am just struggling currently with figuring out what an "ideal solution" looks like to the following problem, and haven't pinned down an equation. I ...
1
vote
1answer
59 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
31 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
50 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
30 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
1answer
25 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
23 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
47 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 ...
1
vote
2answers
107 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
116 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
194 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
38 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
43 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....
5
votes
3answers
285 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
0answers
39 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 ...
1
vote
1answer
103 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
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
412 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 = |$\...