The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
0answers
20 views

Name of a type of code similar to block codes

I've encountered a system where I need to construct a sort of quasi block code: We want to communicate a symbol $s$ from a finite-sized alphabet $\mathcal{S}$ using $N$ segments of information. ...
-2
votes
1answer
20 views

How can I construct a Turing Machine that accepts encoding of another Turing Machine? [closed]

How can I construct a Turing Machine that accepts the language L = <'M'> which is an encoding of a Turing Machine M?
3
votes
1answer
30 views

Turing machine working only with 1's and blanks - how to encode input?

Let's say we have a Turing machine which head can only write 1 or blank to the tape (although it can read all symbols from any input alphabet correctly). Can we operate with it on any input? My ...
0
votes
0answers
12 views

Tidier Iterative Run Length Encoding Algorithm [closed]

The problem is very, very simple: Given an array of objects: [A, A, B, C, C, C, B, B, A] Iterate over the array and perform run length encoding: ...
-2
votes
1answer
28 views

How do I interpret a binary tree generated using Huffman coding algorithm?

In the lecture note here, a binary tree was generated from the huffman algorithm. However it did not explain what this graph mean. From this binary tree, what can we say about the encoding for the ...
1
vote
1answer
40 views

Designing a prefix code for integers?

trying to figure out how to approach this problem. Suppose a sender in a network wanted to communicate the length n of the block it will be using in a subsequent transmission. If there were not ...
0
votes
1answer
39 views

Confusion in “mask bits”

This is the question: By definition of the IEEE754 standard, 32-bit floating point numbers are represented as follows: S (1 bit) E (8 bits) M (23 bits) S: Sign bit E: Exponent M: ...
0
votes
0answers
15 views

G1, G2, H1, H2 are submatrices of the generator and parity check matrices of a code as described below. Can G1 * H2' and G2 * H1' both be all zeroes?

$ G $ and $ H $ are the generator and parity check matrices respectively of a linear block code. Let $ G_1 = G(:, 1:n-s) $ (Matlab style representation of sub matrices). That is, $ G_1 $ is equal to ...
2
votes
1answer
25 views

Typical set in Shannon's source coding theorem

I was following the textbook by David Mackay: Information theory inference and learning algorithms. I have question on asymptotic equiparition' principle: For an ensemble of $N$ $i.i.d$ random ...
2
votes
1answer
55 views

Source Coding Theorem: what happen when go below N⋅H(x) bits?

I was following the text book by David Mackay: information theory inference and learning algorithms, this could be found online on his website. I have question on the source coding theorem (emphasis ...
3
votes
2answers
65 views

Variable Length Encoding of Integers Using a Modulus Algorithm

Continuing on the theme from my last question Variable Length Encoding of Integers, I have come up with a simple encoding scheme, but for which an efficient algorithm eludes me. The constraints are ...
3
votes
1answer
21 views

Lexicographical position of a string in its type class

I have the following problem: Given a string $x\in\{1,...,M\}^+$ of length $n$. Let $S$ be the set of all words with exactly the same numbers of occurences of smybols as in $x$. In fact, $S$ consists ...
0
votes
1answer
81 views

How to store factorials? [closed]

Can someone help me to store the factorial of large numbers such as 100! efficiently? UPDATE: obviously, storing the argument rather than the factorial digits themselves achieves a significant ...
3
votes
2answers
64 views

How does one choose an optimal alphabet for finding a Huffman encoding?

Huffman encoding will perform best when the distribution of symbols of an alphabet that the string to be encoded uses is dyadic. Given an arbitrary bit string S, ...
-1
votes
1answer
24 views

Why do I not get the correct smallest possible value in 2's complement?

When using 2's complement with 4 bits, the largest positive int I can represent is 0111. The smallest negative one is 1000. The smallest int should intuitively be the negative of 0111 - 1 = 0110 ...
2
votes
1answer
198 views

A string representation of any Turing machine

The set of all Turing machines is said to be countable. The central idea of the proof of this fact is that every Turing machine can be written as a finite string of characters. I am having trouble ...
0
votes
1answer
131 views

Precise definition of term: *schema*

Does the term schema, in the context of describing a structure, refer to the actual structure of the data, or the description of this structure? I.e. can I talk about the schema of an entity without a ...
10
votes
1answer
176 views

How do I find the shortest representation for a subset of a powerset?

I'm looking for an efficient algorithm for the following problem or a proof of NP-hardness. Let $\Sigma$ be a set and $A\subseteq\mathcal{P}(\Sigma)$ a set of subsets of $\Sigma$. Find a sequence ...
2
votes
1answer
116 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 ...
-1
votes
2answers
188 views

Finding the difference between two number in a sorted list using divide-and-conquer

How to find the smallest difference between two numbers in a sorted list using divide-and-conquer approach? For example, ...
-1
votes
1answer
352 views

Decoding a binary message with LZW dictionary

I have the following exam question for a multimedia exam in college and I have absolutely no idea where to start. I know how the decoder algorithm should work but I have no idea how to do it on ...
2
votes
2answers
135 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?
1
vote
3answers
2k views

What are two's complement integers?

Can someone explain in plain English what "two's complement integer" means? I read this: in Java long is a 64-bit signed two's complement integer
2
votes
3answers
204 views

Reconstructing files from binary

Popular view tells us that any kind of information is just a collection of bits, that is zeroes and ones placed in a particular order. I was thus having this thought. Suppose that I have some kind of ...
0
votes
1answer
422 views

Jamming signal useless in CSMA / CD?

I'm looking at collision detection in communication protocols, in particular Carrier sense multiple access with collision detection (CSMA/CD). According to what I've read on Wikipedia, a collision ...
3
votes
1answer
133 views

Polynomially related lengths under two different encodings

I'm reading through "Computers and Intractability: A guide to the Theory of NP-Completeness" by Michael R. Garey and David S. Johnson, p. 20 and I came across this ...