We study the optimal generation of random numbers using a biased coin in two cases: first, when bias is unknown, and second, known. In first case, we characterize functions that use discrete source unknown distribution to simulate target variable with given rational distribution. identify minimize ratio inputs outputs. show these are efficiently computable. second prove it impossible construct an tree algorithm recursively, model based on algebraic decision tree. Our computation sufficiently...

In this paper, we characterize functions that simulate independent unbiased coin flips from of unknown bias. We call such randomizing. Our characterization randomizing enables us to identify the generate largest average number fair a fixed biased flips. show these optimal are efficiently computable. Then generalize characterization, and present method an arbitrary rational probability distribution optimally (in terms output digits) computational complexity) outputs many-faced dice...

Peres's algorithm produces unbiased random bits from biased coin tosses, recursively, using the famous von Neumann's method as its base. The is simple and elegant, but, at first glance, appears to work almost like magic generalization elusive. We generalize generate loaded dice, i.e., many-valued Bernoulli source. asymptotically optimal in output rate original algorithm. Three-valued case discussed detail, then other many-faced cases are considered.

We discuss the problem of finding a minimal aliasing code among class systematic single-error-correction codes that are suitable to be implemented within DRAM die, as opposed external ECC used in memory controller outside chip. prove sharp lower bound probability and propose simple method come up with meets bound. By an experiment, we also demonstrate randomly chosen is likely have much more aliasings overwhelmingly high probability.

피어투피어 방식의 스트리밍 기법은 크게 트리-푸시 구조와 메시-풀 구조로 연구가 진행되었다. 하지만 구조는 트리를 재구성하는 지연 시간이 상당히 길어진다는 단점이 있고, 서버와의 재생 시간차가 크며, 초기 시작이 지연되는 단점을 가진다. 본 논문에서는 구조의 장점을 동시에 사용하는 새로운 푸시-메시 기법을 제안한다. 이 기법에서는 기본적으로 구조를 기반으로 높은 네트워크 업로드 성능을 가지는 피어를 최대한 활용한다. 또한, 소스 서버와 수퍼 피어 및 피어와 특정 수의 일반 피어들 사이에 푸시 데이터 전송을 지원한다. 마지막으로 NS-2 시뮬레이터를 이용한 실험을 통해 구조보다 감소하였고, 시간차는 트리와 비슷하며, 연속성은 가장 우수하다는 것을 보였다. The research on peer-to-peer streaming schemes has largely focused tree-push and mesh-pull structures. However, the structure...

Extracting procedures produce unbiased random bits from biased coin flips. Binarizations take inputs an m-faced dice and bit sequences to be fed into a (binary) extracting procedure obtain bits, this can done in entropy-preserving manner, without loss of information. Such has been proposed by Zhou Bruck [1]. We discuss family such processes that we call complete binarizations.

An m-extracting procedure produces unbiased random bits from a loaded dice with m faces, and its output rate, the average number of per input is bounded by Shannon entropy source. This information-theoretic upper bound can be achieved only asymptotically as size increases, certain extracting procedures that we call optimal. Although computationally efficient optimal 2-extracting has been known for while, counterparts m-ary input, > 2, was found recently, they are still relatively complicated...

This paper addresses the problem of constructing scale-space aspect graph a solid revolution whose surface is zero set polynomial volumetric density undergoing Gaussian diffusion process. Equations for associated visual event surfaces are derived, and curve tracing techniques used to delineate these surfaces. An implementation examples presented, limitations as well extensions proposed approach discussed.

본 논문에서는 점근적으로 최적인 두가지의 무작위화 함수인 일라이어스(Elias) 함수와 페레즈(Peres) 함수의 장단점을 고려한 하이브리드 함수를 제안한다. 함수는 편향성이 있는 무작위수의 공급원으로부터 균등한 무작위수를 생성하는데 쓰이는 알고리즘을 수학적으로 추상화한 것이다. 일라이어스 페레즈 입력의 길이가 무한으로 증가함에 따라 그 출력효율성이 정보론적 한계치에 다가간다. 특히, 주어진 (유한의) 입력길이에 대해 함수이다. 그러나 계산은 간단하지 않고, 의존한다. 반면, 정해진 길이에 출력효율이 최적이지는 않으나, 점근적으로는 최적이고, 간단한 재귀식에 의해 정의되어서 계산이 매우 간단하고 적은 메모리를 필요로 한다. 이러한 계산복잡도와 출력효율에 대한 두가지 장단점에 주목하여, 각각의 장점을 제안하고 이를 분석한다. Proposed is a hybrid randomizing function using two asymptotically optimal functions:...

We report a computation of the exact output rate recently-discovered generalization Peres algorithm for generating random bits from loaded dice. Instead resorting to brute-force all possible inputs, which becomes quickly impractical as input size increases, we compute total length on equiprobable sets inputs by dynamic programming using recursive formula.

Peres algorithm applies the famous von Neumann trick recursively to produce unbiased random bits from biased coin tosses. Its recursive nature makes simple and elegant, yet its output rate approaches information-theoretic upper bound. However, it is relatively hard explain why works, appears partly due this difficulty that generalization many-valued source was discovered only recently. Binarization tree provides a new conceptual tool understand innerworkings of original recently-found...

This paper proposes two new encoders for data bus inversion (DBI), which conventionally uses a majority voter to pick representation that minimizes switching activities and thus reduces the corresponding energy consumption. The employ simpler approximate voters comprising only gate levels, improve latency more than twice while still achieving activity savings by 9% 11%, respectively. Although proposed are not always accurate, errors in do affect correctness of movement. We report various...

An m-extracting procedure produces unbiased random bits from a loaded dice with m faces. A binarization takes inputs an m-faced and produce bit sequences to be fed into (binary) extracting obtain bits. Thus, binary procedures give rise via binarization. entropy- preserving is called complete, such has been proposed by Zhou Bruck. We show that there exist complete binarizations in abundance as naturally arising trees leaves. The well-known leaf entropy theorem closely related structure lemma...

이 논문은 무작위수 생성을 위한 페레즈 함수와 같이 재귀적으로 정의된 부 함수에 대하여 논한다. 두 개의 인자함수를 쓰는 대신, 함수들은 한 인자함수만을 이용하여 정의된다. 따라서 당연히 그 출력효율은 비하여 낮고, 점근적으로 최적효율을 내지도 않는다. 그러나, O(n logn)의 시간복잡도를 갖는 비하여, 선형시간, 즉 O(n)의 시간에 실행된다. 더구나, 하나의 쓰기 때문만이 아니라 꼬리재귀함수로서 간단한 반복수행에 의해 구현되어 함수보다 더 적은 메모리로 구현될 수 있다. 그럼에도, 널리 알려진 선형시간 알고리즘인 폰 노이만 방법보다 출력효율이 최대 배 이상 높다. 따라서, 방법들은 모바일 기기와 같은 제한된 계산 자원을 가진 환경에서 방법 대신 이용될 논문에서는 이러한 함수들의 실행시간과 정확한 출력효율을 분석하여, 함수를 비롯한 다른 방법들과 비교한다. 그리고, 구현에 We study sub-Peres functions that are defined...

In a recent work, Bernardini and Rinaldo generalize attempt to improve upon Elias method obtain unbiased random bits from geometric distribution resulted Poisson process. As response, we analyse the output rates of their compare with original binary app lied on Bernoulli process same process, which turns out be much simpler implement have higher rate.

Data bus inversion (DBI) is an encoding technique that saves power in data movement which the majority function plays essential role. For a latency optimization, can be replaced by approximator allows for small error voting to obtain faster encoder still power. In this work, we propose two systematic approaches finding high-performance approximators. First, perform exhaustive search of all possible Boolean functions find optimal based on certain circuit structure comprised fifteen logic...