Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [encoding-scheme]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
18 views

A specification of all possible languages for representing graphs?

There are a few commonly used markup languages for specifying graph structures. I am interested in discovering alternative graph notations that may be counterintuitive yet more compact or useful in ...
Julius Hamilton's user avatar
0 votes
0 answers
52 views

Kolmogorov complexity of tuples

Exercise 14.1 of Elements of Information Theory asks us to prove that there is a constant c such that $$K(x,y)\leq K(x) +K(y)+c$$ for all binary strings $x,y$. Intuitively this seems true. Just write ...
Caspar's user avatar
  • 1
0 votes
0 answers
11 views

Determining the benefit from increasing bits available in base 32 checksum

I'm looking at using something like Crockford Base-32 encoding in a situation where people have to manually write IDs in a very compact space. Crockford Base-32 describes a simple checksum algorithm ...
anjama's user avatar
  • 181
1 vote
0 answers
96 views

Succint data structure for storing n numbers using a mask-based partition

I've a set $N$ of $n$ distinct numbers of $d$-bits each; call them words ($1\leq n\leq 2^d$, with $d\geq 1$). I want to store $N$ using as least space as possible, by partitioning $N$ and factoring ...
ABu's user avatar
  • 529
1 vote
2 answers
108 views

Memory-efficient representation of keys over a huge domain

I don't know if the title of the question is accurated or not, but I was thinking of the following problem: I have a set of numbers, let's call them identifiers. Each identifier is stored on a 64-bit ...
ABu's user avatar
  • 529
1 vote
1 answer
46 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 ...
Yannik Eik's user avatar
0 votes
0 answers
71 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 ...
Sahil Sharma's user avatar
1 vote
1 answer
97 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 ...
ryan chandra's user avatar
-1 votes
2 answers
88 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 ...
Toothpick Anemone's user avatar
0 votes
1 answer
69 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 ...
Jayendra Parmar's user avatar
1 vote
2 answers
51 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 ...
chausies's user avatar
  • 532
-1 votes
1 answer
53 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 <...
lesobrod's user avatar
  • 111
0 votes
3 answers
345 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 ...
Sajeev Pillai's user avatar
1 vote
1 answer
52 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, ...
Colim's user avatar
  • 131
1 vote
1 answer
492 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 ...
PandaPhi's user avatar
  • 131
1 vote
1 answer
48 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#...
user363406's user avatar
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 ...
Oleg Dats's user avatar
  • 299
1 vote
3 answers
441 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 ...
Artyom Vorontsov's user avatar
0 votes
1 answer
33 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 } &...
Rico1990's user avatar
  • 125
0 votes
4 answers
187 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 ...
Qwertyluk's user avatar
  • 111
3 votes
1 answer
113 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 ...
Meta_Alchemy's user avatar
2 votes
1 answer
246 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 ...
programonkey's user avatar
2 votes
4 answers
175 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 ...
Lewec's user avatar
  • 23
1 vote
2 answers
35 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 ...
Moonwalker's user avatar
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 ...
SapereAude's user avatar
0 votes
0 answers
158 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)$,...
roydiptajit's user avatar
1 vote
2 answers
221 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 ...
user111064's user avatar
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}$ ...
fhm's user avatar
  • 21
2 votes
0 answers
41 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 ...
chrisper's user avatar
2 votes
1 answer
78 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]...
user110001's user avatar
2 votes
1 answer
69 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 ...
Black Jack 21's user avatar
1 vote
2 answers
51 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 ...
Lance's user avatar
  • 2,233
2 votes
1 answer
162 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 ...
awezmm's user avatar
  • 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 ...
Timone's user avatar
  • 459
0 votes
0 answers
199 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 ...
Zirui Wang's user avatar
2 votes
1 answer
109 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 ...
Black Jack 21's user avatar
0 votes
1 answer
459 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 ...
Black Jack 21's user avatar
2 votes
1 answer
963 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: ...
user avatar
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 ...
SE - stop firing the good guys's user avatar
2 votes
1 answer
55 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 ...
Mahathi Vempati's user avatar
0 votes
1 answer
160 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 ...
Link L's user avatar
  • 481
2 votes
0 answers
85 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?
David Roonie's user avatar
2 votes
3 answers
330 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 ...
Costantino Grana's user avatar
1 vote
2 answers
207 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 ...
Michael's user avatar
  • 291
-2 votes
1 answer
116 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 ...
J B's user avatar
  • 3
0 votes
3 answers
2k 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 ...
Omar Ibrahim Culé's user avatar
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 ...
Michael's user avatar
  • 291
1 vote
1 answer
48 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 ...
Devharsh Trivedi's user avatar
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, ...
DenverCoder1's user avatar
1 vote
1 answer
100 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 ...
Zirui Wang's user avatar