The Optimized Cascade Protocol Sample Clauses

The Optimized Cascade Protocol. − Xxxxxxxx and Xxxxxxxx did more work on the Cascade protocol in [73]. Observing the simulation results of Cascade, they found that almost all errors are corrected during the first two passes, and only very few errors were left for further passes to correct. Another observation is that almost half of the errors are removed in Pass 1, and the other half in Pass 2. The block lengths w1 and w2 are selected to minimize the number of publicly exchanged parities. After Pass 2, the BICONF primitive is employed in each pass to correct the few remaining errors. We call such a pass a BICONF pass. When one error is found in a BICONF Pass i, where i > 2, other errors may also be corrected by going back to blocks of previous passes that contain the newly corrected error. If no error is detected after l subsequent passes, Xxxxx’s string will agree with Bob’s with probability at least 1 2—l. There are np errors in Bob’s string on average. If half of the errors are corrected in Pass 1, then the expected number of parities exchanged is L(Pass 1) = n + np log(w ). (2.21) exp w1 2 1 The other half is corrected by pairs in Pass 2. For any pair of errors, one is corrected in some block of Pass 2, where log(w2) more parities are expected to be exchanged, while the other in some block of Pass 1, where about log(w1) more parities are expected to be exchanged. Therefore, the expected number of parities in Pass 2 is The optimal values w1 = j 4 ln 2 k and w2 = j 4 ln 2 k are determined by minimizing L(Pass 2) = n + np [log(w ) + log(w )] . (2.22) exp w2 4 1 2 exp exp 3p p L(Pass 1) + L(Pass 2) . Later, Xxxxxxxx and Xxxxxxxx made a further improvement, because the number of corrected errors in Pass 1 and Pass 2 is not half to half when p is large (for example p = 0.15). According to (2.18), the probability that an error can be detected in a block of Pass 1 is given by Xxxx = 1 − (1 − 2p)w1 . − · · There are n/w1 blocks, so about Xxxx n/w1 errors are expected to be corrected in Pass 1, and xx Xxxx n/w1 errors are left for Pass 2. Therefore, (2.21) and (2.22) should be replaced by the following two equations + n · Xxxx log(w ). (2.23) exp w1 w1 1 exp w2 2 w1 1 2 L(Pass 2) = n + 1 np − n · Xxxx [log(w ) + log(w )] . (2.24) exp exp The optimal w and w are obtained by minimizing L(Pass 1) + L(Pass 2) . There are no explicit formulas for w1 and w2 in this case, but numerical optimal values for w1 and w2 can be obtained. We show the block lengths w1 and w2 in Table 2.1 compared with those i...