From - Sun Dec 31 21:23:31 2000 Path: reader4.news.rcn.net!feed1.news.rcn.net!feed2.news.rcn.net!rcn!news.maxwell.syr.edu!wn4feed!worldnet.att.net!135.173.83.72!wnfilter2!worldnet-localpost!bgtnsc07-news.ops.worldnet.att.net.POSTED!not-for-mail From: "Stephen Fuld" Newsgroups: comp.arch References: <918g9r$19q$1@nnrp1.deja.com> <91f5jb$80o$1@rocky.jgk.org> <3A3B75B8.31DD9104@moreira.mv.com> <977174086.645306@haldjas.folklore.ee> <3A3F6B2A.1C98807B@moreira.mv.com> <91tpcn$s6u$1@news7.svr.pol.co.uk> <91tutt$31v$1@pyrite.mv.net> <3A43E034.129C5BEE@hda.hydro.com> <921br3$n70$1@pyrite.mv.net> <3A44EB37.3CEC0ED8@hda.hydro.com> <925k89$t8b$1@pyrite.mv.net> <3A467BCC.63965D7F@hda.hydro.com> <7HN16.4878$bU.333212@bgtnsc04-news.ops.worldnet.att.net> <3A48BCAF.C00961E9@hda.hydro.com> <3A4E3F99.2AEA295B@mcclatchie.com> Subject: Re: 4M pages are a bad idea (was Re: AMD 64bit Hammer CPU and VM) Lines: 103 X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 5.00.2919.6600 X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2919.6600 Message-ID: Date: Sun, 31 Dec 2000 05:49:08 GMT NNTP-Posting-Host: 12.72.232.47 X-Complaints-To: abuse@worldnet.att.net X-Trace: bgtnsc07-news.ops.worldnet.att.net 978241748 12.72.232.47 (Sun, 31 Dec 2000 05:49:08 GMT) NNTP-Posting-Date: Sun, 31 Dec 2000 05:49:08 GMT Organization: AT&T Worldnet Xref: reader4.news.rcn.net comp.arch:122323 "Iain McClatchie" wrote in message news:3A4E3F99.2AEA295B@mcclatchie.com... > Stephen> But it is true that the number of bits of ECC scales much > Stephen> less than linearly with the number of bits over which the > Stephen> ECC protects. Thus there will be far fewer than twice the > Stephen> number of ECC bits for twice the number of data bits, all > Stephen> other things equal, [....] > > Interesting stuff, Stephen, but I think your first sentence is > misleading. As the number of bits protected by a Reed-Solomon code > increases, the number of parity bits must increase even more, if you > wish to cover the same expected error rate. > > Imagine that we have two blocks of length n, each seperately covered > by a Reed-Solomon ECC, so that we can tolerate t errors in each block. > Let's say E is the number of correctable error syndromes for each > block. Then E^2 is the number of correctable error syndromes for > both blocks. > > If instead we try to cover 2t errors with a Reed-Solomon block of > length 2n, we'll have more than E^2 correctable error syndromes, > because the code is now covering cases like all 2t errors showing > up in the first half of the 2n block. We're getting better coverage, > so we have to pay with more error-correcting bits somehow. We'll > pay by having larger parity symbols. > > Here's the RS code similar to what they probably use now: > > Code A: > Symbol size: 9 bits > Block length: 510 symbols (= 4590 bits or about 573 bytes) > Parity symbols: 54 symbols > Data symbols: 456 symbols (= 4104 bits or about 513 bytes) > Correctable errors: 27 > > For 512-byte blocks, you obviously have to stick with 456 data > symbols, but you can elide pairs of parity symbols, each time losing > the ability to correct one symbol in error, if you want smaller > blocks. > > Here's what you could scale up to, to handle a larger BER: > > Code B: > Symbol size: 11 bits > Block length: 2046 symbols (= 22506 bits or about 2813 bytes) > Parity symbols: 556 symbols > Data symbols: 1490 symbols (= 16390 bits or about 2048 bytes) > Correctable errors: 278 > > A subset that's roughly comparable to code A would be > > Code C: > Symbol size: 11 bits > Block length: 1707 symbols (= 18777 bits or about 2347 bytes) > Parity symbols: 216 symbols > Data symbols: 1491 symbols (= 16401 bits or about 2050 bytes) > Correctable errors: 108 > > Here code C covers about the same error rate as code A, but notice > that we have more parity BITS. The number of parity symbols is > roughly linear with the number of data bits protected, but those > symbols grow larger as the number of data bits grows. So it's more > than linear, not less. > > Lin and Costello, "Error Control Coding: Fundamentals and > Applications", p. 171 has the scoop on RS codes. Keep up the > interesting posts. Thanks, Ian. I see the problem. You are right, my sentence was misleading. What I meant to say, (or perhaps should have said) is if the number of bits corrected is the same, then the number of parity bits scales less than linearly. Your interesting analysis above shows that if the number of bits corrected _per data bit_, (essentially the tolerable error rate) remains the same, then the number of parity bits required actually increases with the number of data bits. I did not know that. Thanks for the exposition. I'm not sure, in practice, which analysis is more meaningful. I suspect it depends on the error characteristics of the disk system. If erorrs are really very few, then the probability of >N (where N is the number of error bursts tolerable in a short record) occurring within the same (larger) record is small and my statement of the problem is more applicable. If the error rate is higher to the point where the probability of >N bursts occuring in the longer records is significant, your analysis is more applicable. Since the point of the sub group was to evaluate longer records in order to decrease the overhead of ECC, then they (the coding experts, of whom I was most certainly NOT one) must have thought they could use fewer ECC bits per data bit in the longer records. That was what led to my statements. -- - Stephen Fuld > > -Iain McClatchie 650-364-0520 voice > http://www.10xinc.com 650-364-0530 FAX > iain@10xinc.com 650-703-2095 cell