We present three techniques for extracting entropy during boot on embedded devices. Our first technique times the execution of code blocks early in the Linux kernel boot process. It is simple to implement and has a negligible runtime overhead, but, on many of the devices we test, gathers hundreds of bits of entropy. Our second and third techniques, which run in the bootloader, use hardware features - DRAM decay behavior and PLL locking latency, respectively -- and are therefore less portable and less generally applicable, but their behavior is easier to explain based on physically unpredictable processes. We implement and measure the effectiveness of our techniques on ARM-, MIPS-, and AVR32-based systems-on-a-chip from a variety of vendors.

In this paper an optimal importance sampling (IS) method is derived for a transient Markov system. Several propositions are presented. It is shown that the optimal IS method is unique, and it must converge to the standard Monte Carlo (MC) simulation method when the sample path length approaches infinity. Therefore, it is not the size of the state space of the Markov system, but the sample path length, that limits the efficiency of the IS method. Numerical results are presented to support the argument.

We introduce the problem of constructing good fast recovery convolutional codes. When the constraint lengths of the candidate codes are long (say more than 12), it is too computationally complex to perform the code search task. Fortunately, we can transform the code construction problem to a problem related to a transient Markov system. We then develop an optimal importance sampling (IS) method to fulfil the tasks. In this article, we also prove several propositions for optimal IS. For instance, we show analytically that the optimal IS method is unique. We prove that the optimal IS method must converge to the standard Monte Carlo (MC) simulation method when the sample path length approaches infinity. This finding shows that it is not the size of the state space of the Markov system, but the sample path length, that limits the efficiency of the IS method. Based on insights from the optimal IS method, a suboptimal IS method is then proposed to search for long fast recovery codes. The suboptimal method can achieve a substantial speedup gain. After that, several numerical results are presented to study the efficiency of the IS methods and to justify the code search procedures. Finally, we give the code search results and the application of these codes.

In this paper, we study importance sampling (IS) methods to construct long convolutional codes with fast recovery capability. For codes with long memory length (m/spl ges/12), the simulation method based on IS can avoid the excessive amount of computation required by other methods like analytical computation and standard Monte Carlo simulation. We establish a suboptimal IS method to search for good fast recovery convolutional codes with long memory lengths. The speed-up factors of two to six orders of magnitude over standard Monte Carlo simulation are obtained. Finally, we outline the code search procedures, present the code search results and give some applications of the codes.