Tag Info

Hot answers tagged

6

Primes are rare, but numbers with large prime factors are common. If $n$ is around $2^{100}$, it will take about 100 bits to represent it in the usual base-2 way. It will take more than 100 bits to represent it your way, if it is divisible by any prime exceeding the 100th prime, and most numbers in the neighborhood of $2^{100}$ are divisible by some prime ...


4

Take $N$ large. Then the number of integers in $[1,N]$ which have a prime factor greater than $\sqrt N$ is asymptotic to $N \log 2$ (see http://en.wikipedia.org/wiki/Dickman_function). These numbers all require at least $\pi(\sqrt{N}) \sim 2 \sqrt{N}/\log N$ bits. Therefore the average number of bits used will be asymptotically at least as high as $(2\log ...


3

It depends on what you mean by a binary representation of all numbers and by most compact. One interpretation is a mapping $\varphi$ from the natural numbers to binary strings such that given a binary string encoding possibly more than one number, there is at most one way of decoding it. For example, suppose we encode the numbers $0,1,2,3,\ldots$ using the ...


2

A channel with 90% of its bits deleted is still capable of transmitting information. For example, you can send one bit by sending it a hundred times. You can probably send more bits this way, say by transmitting $0^{100} 1^{100}$ for 0 and $0^{200} 1^{100}$ for 1. This still doesn't show that the capacity is positive, but makes it seem reasonable. This ...


1

is there a code that can detect multiple errors Of course there are. As Snowball points out, repetion codes are a (rather trivial and not very efficient) example. The main classical families of practical codes are Cyclic Codes (which have the additional feature of detecting longer burst errors), BCH and Reed-Solomon -and related- codes (actually these ...


1

From what I can tell, they're designed to exclusively detect the location of a single error, and the presence of two errors. For binary codes, detecting the location of an error is the same as correcting the error (flip the bit at the detected location). Because of this, such a code is usually called $1$-error-correcting. Similarly, detecting the ...


1

$$ I(X;Y|Z) = \sum_{x,y,z}p(x,y,z)\log{p(x,y|z)\over p(x|z)p(y|z)} $$ so it isn't either of those things, but the mutual information between $X|Z$ and $Y|Z$ is a better description. [Reference: equation (2.118) of Information Theory and Network Coding by R. Yeung.]



Only top voted, non community-wiki answers of a minimum length are eligible