| System and method for estimating probabilities of events -> Monitor Keywords |
|
|
 
System and method for estimating probabilities of eventsRelated Patent Categories: Pulse Or Digital Communications, ReceiversSystem and method for estimating probabilities of events description/claimsThe Patent Description & Claims data below is from USPTO Patent Application 20060193400, System and method for estimating probabilities of events. Brief Patent Description - Full Patent Description - Patent Application Claims
REFERENCE TO RELATED APPLICATIONS [0001] This application claims the benefit of provisional U.S. Patent Application No. 60/486,970, filed Jul. 14, 2003. BACKGROUND OF THE INVENTION [0003] 1. Field of the Invention [0004] The present invention relates to estimating the probabilities of events and, more particularly, to a dual adaptive importance-sampling system and method. [0005] 2. Background of the Related Art [0006] In the field of communications engineering, the performance of forward error correction (FEC) codes in digital communication systems is almost exclusively studied and compared on the basis of performance curves--plots of bit-error rate (BER) and/or word-error rate (WER) versus the information signal power to noise power ratio (SNR). [0007] The exact analytical evaluation of FEC code performance curves under a specific decoding scheme is extremely difficult to perform and computationally intractable, even for moderately long codes, say with more than 30 to 40 information bits per codeword. [0008] Approximate performance of FEC codes under certain decoding schemes, in the form of lower and upper bounds, may be obtained analytically provided knowledge of the weight enumerator function (WEF) of the code is available: partial knowledge of the WEF in the form of the first non-trivial term may also suffice. In general, these bounds serve as very good approximations to the actual code performance at high SNR values. The quality of the approximations, however, is not very good at relatively moderate-to-low values of SNR. To make matters worse, unless the code belongs to one of the few classes of codes whose WEF is already known, such as the RS and BCH codes that still abound in practical FEC schemes, the computation of the code WEF or even the first non-trivial term is itself intractable, in a practical sense, for codes of practical size. [0009] Thus, in general, for a large set of codes with parameters in the realm of current practical applicability (hundreds and thousands of bits long), it is impossible for FEC code researchers and developers to analytically obtain performance curves, either exact or in the form of bounds. Consequently, for some time now, the preferred methodology employed by communications engineers and researchers to study code performance has and continues to be based on performing Monte Carlo computer simulations or physical system experiments. For the simpler and less powerful codes, simulation software packages, such as Mathwork's MATLAB or Elanix's System View, provide communications oriented simulation tools (e.g., MATLAB's Communication ToolBox and SimuLink) that perform straight Monte Carlo simulation of BERs. [0010] Monte Carlo simulations and physical system experiments, which are collectively referred to herein as "standard Monte Carlo techniques", have been quite effective in obtaining performance curves down to BER values as low as approximately 10.sup.-7. These BERs are consistent with performance requirements for such communication systems as ADSL and wireless phone systems. Attempting to obtain performance curves for lower values of BER, however, continues to be a challenge even with current computing capabilities because of the inordinate amounts of time required--on the order of months or years--to obtain meaningful results at such low BER values. [0011] Recent technological advancements have drastically altered the scenario in the communications industry. The industry has witnessed an explosion in communications speeds and capacity of storage media, in addition to improvements in the overall quality of communications. This has led service providers to impose more stringent requirements on the error rate of communication systems, e.g., current optical fiber communication (OFC) systems operate at design BERs in the range of 10.sup.-12 to 10.sup.-15. Unfortunately, standard Monte Carlo techniques prove to be inadequate for evaluating FEC codes and decoders at such low BER values. [0012] In an attempt to extend the range of standard Monte Carlo techniques and provide some assistance in the evaluation of higher performing systems, researchers have called upon the services of supercomputers or system experiments. Both of these approaches are characterized by unduly long performance time requirements and, even then, the best reliable BERs that have been achieved are on the order of 10.sup.-10 or 10.sup.-11 and are acquired over time spans measured in months. This is very expensive to industry and researchers in terms of person hours and computer time. [0013] The evaluation of BERs for an actual physical system, e.g., an exploratory development prototype, invariably involves the use of a bit-error-rate tester (BERT). BERTs designed to operate at the extremely high speeds of 40-48 giga-bits per second (Gbps) have been recently introduced in the market. They are capable of operating at `full line rate`, i.e., these BERTs can count each and every transmitted (and received) bit at speeds of up to 40-48 Gbps. With such devices, one can easily transmit and receive about 10.sup.15 bits in a period of about 2.5.times.10.sup.4 seconds (i.e., <7 hours), thus enabling the evaluation of BERs reliably at least down to 10.sup.-13 (100/total number of bits) within a relatively short period of time. However, such BERTs are extremely expensive, costing on the order of $500,000. [0014] In coded communication systems with long codes, the range of word-error rates (WERs) that can be reliably evaluated is less than the uncoded system by a factor equal to the length of the code. For example, consider a code of length n=1.1.times.10.sup.3, with k=10.sup.3 information bits and a rate of r=0.909, employed on a communication system operating at an information transfer rate of 40 Gbps (i.e., a line rate of 40/r=44 Gbps). Transmission and reception of 10.sup.15 information bits would require about 2.5.times.10.sup.4 seconds. However, 10.sup.15 information bits correspond to only 10.sup.12 codewords. Thus, a reliable estimate of WER only down to 10.sup.-10 is possible. Further, if one assumes that every word that is not correctly decoded results in about 10 information bits in error (the average number of information bits in error per codeword in error is dependent on the minimum distance of the code and other code properties), one realizes that the transmission of 10.sup.15 information bits is capable of providing us with reliable BERs only down to 10.sup.-12, instead of the 10.sup.-13 that was possible in the uncoded system. The situation is further worsened as the code length increases. In addition to the above problem, the use of high-speed BERTs in conjunction with system experiments for evaluating the performance of coded communication systems is severely limited by a host of other constraints. [0015] First, evaluation of a code at such high speeds requires that encoder/decoder hardware implementations capable at operating at the above-mentioned speeds be available. The fastest encoder/decoders available today operate around 1 Gbps. Consequently, practical coded communications systems that operate at speeds in the range of 10-40 Gbps require the multiplexing/demultiplexing of FEC encoder/decoders at the transmitter and receiver, thus increasing the complexity of the system. Further, fabricating encoder/decoders for any code that needs to be evaluated is generally not economically feasible because of the cost of manufacturing high-speed VLSI devices and the almost universal approach of software implementation for initial design and evaluation. To complicate matters even more, the new class of decoders use soft-information to perform soft-decision decoding. This information is obtained by multi-threshold-decisioning on the received signal, and is difficult to extract--commercially impractical--at 10-40 Gbps operating speeds. This virtually eliminates the possibility of evaluating soft-decision decoding performance of FEC codes using high-speed BERTs. [0016] In addition, the high-speed BERTs are themselves quite expensive, i.e., the cost of the Ixia 2.4 Gbps BERT is greater than $10,000.00. BERTs capable of operating at higher speeds are even more expensive (e.g., about $500,000 for the 40-48 Gbps model). The costs of the BERT, of fabricating the encoder/decoders, of the auxiliary equipment, and of setting up the test-bench to evaluate the code, becomes prohibitive, making it practically impossible for researchers and small companies to evaluate their codes to the desired low values of BER using a physical system setup employing BERTs. [0017] A variety of simulation techniques have been developed to evaluate FEC codes to progressively smaller BER values. One of the most promising areas in this context has been the study of importance sampling (IS) techniques. Importance sampling is based on increasing the frequency of occurrence of very low (important) error events defined by the channel noise probability density function (pdf) by generating these important events more frequently from a related biased pdf. However, for importance sampling to be effective for evaluating FEC codes and decoders, one must choose a biased pdf using some knowledge of which noise realizations are most likely to generate errors at each desired low BER. [0018] The task of determining an appropriate biased pdf is FEC code specific. Most of the proposed techniques for evaluating FEC codes via importance sampling rely on using some code-property to obtain a rough estimate of the region in noise space that is a major contribution to the BER. For example, some techniques exploit the knowledge of the minimum-weight codewords to determine a suitable biased pdf. However, as discussed above, this knowledge is practically unobtainable for codes in general. [0019] One technique, described in T. Yamane and Y. Katayama, "Bit Error Rate Analysis on Iterative Two-Stage Decoding of Two-Dimensional Codes by Importance Sampling", Proc. 2003 IEEE Int'l. Conf. Commun., 11-15 May 2003, Anchorage, Ak., USA, uses knowledge of the error-correcting capability of codes (a code parameter that may not be known in general) in order to obtain a suitable biased pdf for IS. This technique is restricted to hard-decision decoding, and is particularly suited only for obtaining performance curves for serially concatenated coding schemes (product codes), where it is possible to easily characterize the error correcting capability of the constituent codes. [0020] Another technique, described in B. Xia and W. E. Ryan, "On importance sampling for linear block codes", Proc. 2003 IEEE Int'l. Conf. Commun., 11-15 May 2003, Anchorage, Ak., USA, use the regular structure of the bipartite graphs of certain codes to determine the biased pdf. For every codeword that is received, the BER evaluation using this IS technique is performed for only a single bit-position in the codeword. Standard Monte Carlo techniques, on the other hand, evaluate the BER for all n bit-positions for every received codeword of length n. [0021] Hence, for the transmission and decoding of the same number of codewords (which can be assumed to take the same time for both IS as well as standard Monte Carlo techniques), the standard Monte Carlo technique evaluates n times as many bits as this IS technique. This is referred to as the `divide-by-n` problem. This divide-by-n problem is likely to affect the efficiency of this IS technique relative to the standard Monte Carlo techniques for codes where n becomes large. In addition, this IS technique is predicated on the regular structure in the bipartite graph of codes, which justifies the analysis of a single bit-position in the code to estimate the BER of the entire code. A regular bipartite graph structure is obtained from regular low-density parity-check (LDPC) codes, but is usually not consistent with irregular LDPC codes or codes in general. [0022] Accordingly, the IS techniques described above are inefficient and/or impractical for very-low-BER-requirement evaluation of arbitrarily chosen codes. Thus, there is clearly a technological need for a more time-efficient simulation tool for evaluating the BERs/WERs of coded communication and storage systems, as well as a tool for evaluating the probabilities of other rare events. SUMMARY OF THE INVENTION Continue reading about System and method for estimating probabilities of events... Full patent description for System and method for estimating probabilities of events Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this System and method for estimating probabilities of events patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like System and method for estimating probabilities of events or other areas of interest. ### Previous Patent Application: Optical communication device Next Patent Application: System for coherent demodulation of binary phase shift keying signals (bpsk) Industry Class: Pulse or digital communications ### FreshPatents.com Support Thank you for viewing the System and method for estimating probabilities of events patent info. IP-related news and info Results in 0.46701 seconds Other interesting Feshpatents.com categories: Novartis , Pfizer , Philips , Polaroid , Procter & Gamble , 174 |
 * Protect your Inventions * US Patent Office filing 
PATENT INFO |
|
