Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [encoding-scheme]

The tag has no usage guidance.

2
votes
1answer
20 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 \...
0
votes
0answers
18 views

BPSK modulation and convolutionally encode binary data with MATLAB [closed]

I am running a simulation to transmit a decimal number with RF transmission converted in binary. Due to simulation type I would like to implement between transmitter and receiver a codification ...
1
vote
0answers
23 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 "...
20
votes
3answers
4k 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
15 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
24 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
16 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 ...
0
votes
1answer
30 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
43 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
84 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
33 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
37 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
205 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
36 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
91 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
61 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 ...
0
votes
1answer
250 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 = |$\...
6
votes
1answer
425 views

Optional prefix code for the naturals

The naturals $\mathbb{N}$ can be encoded with a binary unary code such as $$ \begin{align} 1&=0_b\\ 2&=10_b\\ 3&=110_b\\ &... \end{align} $$ The length this the ...
1
vote
1answer
62 views

What is responsible for the 1-1 correspondence between characters and binary?

Could someone explain to me what component(s) are responsible for translating binary into ASCII/UNICODE? For example, is it an assembly program that sets up a 1-1 correspondence between characters and ...
0
votes
0answers
23 views

LDPC:How to detect total number of errors in a codeword using minimum distance?

Currently, i working with LDPC for FPGA implementation. I have formed H matrix of size 102X204 (N=204,K=102,M=102,R=0.5). Doubt in Error detection and correction for bigger matrix. I know that code'...
0
votes
0answers
41 views

Implementing a decoding algorithm for directed figure codes

I have to implement algorithm, where definitions, input and output of program go as follows: $Σ$ - finite, non-empty alphabet A translation in $Z^2$ by vector $u = ( u_x , u_y ) ∈ Z^...
6
votes
2answers
170 views

Can nested structures be encoded more “readably” with a single delimiter?

Imagine you have two systems of delimiting. One with paired delimiters, [ and ]: [abc] ...
1
vote
1answer
84 views

Calculating the information density of an encoding system

How do I calculate the information density of an encoding system? This question came up as I was reading several papers about encoding data in DNA (I think I have gone through just about every major ...
5
votes
1answer
333 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 ...
0
votes
1answer
192 views

How to encode a sequence of non-decreasing integers with an integer without redundancy, loops, and recursions

How to encode a sequence of n non-decreasing integer of [0, ..., m] fulfilling the following conditions: no or minimal redundancy only use 1 integer variable or k independent integer variables with a ...
0
votes
0answers
29 views

algorithm for encoding segmentations in RGBA data

I'm trying to figure out a good way of encoding object segmentation data into a single RGBA image. I'd like to not only distinguish between classes, but also individuals within classes, and be able to ...
1
vote
1answer
102 views

What should be the way to design code for such a situation?

I have a graph as given below: Let us assume one node as transmitter and another as receiver. We need to transfer particles in every time slot constrained by maximum particles N and minimum 0. The ...
0
votes
2answers
678 views

Understanding the binary and hexadecimal representations of UTF-8

Here is a code point: U+091D. The symbol it represents in UTF-8 is झ. In hex the symbol requires three bytes: e0 a4 9d. But it ...
0
votes
1answer
101 views

Encode an ascii string in base 15

How can I encode an ascii string in base 15? In other words, I have the following characters available: 0123456789abcde I have no idea how to do this. What do ...
5
votes
1answer
159 views

Prefix encoding of algebraic data types

I'm new to coding theory and formal proofs, and am struggling to understand how to construct and reason about prefix-free encoding algorithms on algebraic data types. I hope it's clear if I use ...
2
votes
3answers
160 views

Integer linear programming formulation of formula in DNF

I have multiple sets, e.g., $$\{1, 2\}, \{2, 3, 4\}, \{1, 4\}$$ Each variable $1, 2, 3, 4$ is binary. I need to represent the following condition without additional variables $$(1 \land 2) \lor (2 \...
2
votes
2answers
63 views

Unique representation of 5-number sets with values 1-13

From a simulation I get 5 numbers 1-13. The nature of the simulation is that I do not get the numbers ordered. The value/rank of the the tuple is not order dependent 5 5 5 2 2 = 2 5 2 5 5. Values ...
1
vote
2answers
75 views

Unary encoded language set

While reading the book theory of computation by Michael Sipser, I did not understand the language given below. I will explain the problem first $$L = \{1^n :n \in \mathbb{Z}\}$$ Where $\mathbb{Z}...
1
vote
1answer
229 views

$2^1 + 2^2 + \cdots + 2^8$ in binary

Maybe these are silly question. I know almost nothing about computer science, so please let me know in the comment section if I should edit anything or delete it. Let's say I have a function that ...
0
votes
0answers
29 views

Error Detection Distance of Residue Codes

Given a residue code representing a number N with the tuple (N, R(N))where R(N) equals ...
2
votes
1answer
336 views

integer = c lg n (inputs of size n, Cormen 3rd, page 23)?

I just started with my "Algorithms" course. But my CS-background is lower than that of an average CS-student (I'm a data science student). Only had intro-2-prog course (Python/Java), that's it. ...
2
votes
1answer
134 views

How to uniquely encode a vector of non-increasing positive integers

Given a vector of positive integers $A=[a_1, \cdots, a_n]$, where $\sum_{1 \leq i \leq n}a_i = n(n-1)$ and $a_i \geq a_j$ iff $i \geq j$, I am interested in encoding the vector, maintaining the ...
1
vote
1answer
105 views

Given a binary matrix, how to find the starting coordinates of a sub matrix?

Say, I have an image of bit depth 1 (i.e. binary matrix) and I cropped the image to form a smaller matrix. From the cropped matrix (of a reasonable size). I need to know the starting coordinates from ...
6
votes
1answer
170 views

Error correcting permutation code

Let's say you have $n$ symbols. You can encode a $\log_2(n!)$-bit message by permutating the symbols. I will call this a permutation code (if you have seen this concept before, I would love to see a ...
2
votes
3answers
334 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 ...
8
votes
1answer
262 views

Understanding compression/encoding in linear time

I'm reading the paper N. J. Larsson, A. Moffat: Offline Dictionary-Based Compression, which describes a compression algorithm that, if I understand it correctly, is quite similar to Byte pair encoding....
1
vote
0answers
315 views

Encoding Turing machines in binary in a simple way that gurarentee unique readability

I may come across something like (let $X$ be a binary representation of a Turing machine $M$), I know that we can easily encode the description of the machine as sequence of numbers (by assigning a ...
2
votes
0answers
49 views

Typed representation of a memory model

Assume a simple procedural language, where statements write and read from local memory via references and procedures accept arguments of n different scalar types (say floats, ints and strings) and ...
1
vote
0answers
166 views

Number of unique prefixes in canonical huffman tree

I am trying to implement decompression algorithm based on huffman trees. I am trying to validate my assumptions. Assume that you have alphabet of 350 symbols. Maximum encoded code length is 15 bits. ...
1
vote
0answers
75 views

Byte Stuffing, escaping a flag at maximum frame

I want to encode a message using byte stuffing where every frame delimited by a flag byte 'F' at both ends and escape code equal to the character E. I am trying to encode the message 'DEEP-FRIED-...
3
votes
1answer
4k views

When would the worst case for Huffman coding occur?

I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the ...
1
vote
0answers
138 views

How to encode each possible b-tree of a sequence of n numbers?

Lehmer codes can be used to encode each possible permutation of a sequence of n numbers. Often the main goal is just to map a range of numbers from 1 to x to the possible permutations of a sequence of ...
3
votes
1answer
72 views

How many independent yes/no questions can be asked about a point in binary space (linear vs nonlinear codes)?

This question springs from thinking about the potential benefits of using nonlinear codes instead of linear codes. Say we have a point $x \in \{0,1\}^k$ and we want to guess what it is. A naive scheme ...