Grenzen aan de complexiteit?

Moderator: Xenion

Gebruikersavatar
Berichten: 4.216

Grenzen aan de complexiteit?

Is het zo dat er een bovengrens kleiner dan 1 is aan de betrouwbaarheid "b" die voor logische modules (AND' s, NAND' s, OR' s, etc.) praktisch haalbaar is? Hierbij versta ik onder b de relatieve frequentie waarmee de module het juiste antwoord geeft. Zo ja – dan zou een computer of software niet meer goed kunnen werken zo gauw het totale aantal modules of rekenstappen in de buurt van 1/(1 – b) komt. Zijn er schattingen van te maken wanneer dat punt bereikt wordt?

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.
Gebruikersavatar
Berichten: 2.627

Re: Grenzen aan de complexiteit?

Uiteraard is er een praktische bovengrens aan de betrouwbaarheid, want niks in het leven is zeker. Om een voorbeeld te geven: tijdens de berekening kan er bliksem in slaan in je computer, die alles door de war schopt. Ook kun je denken aan quantummechanische fluctuaties. Uiteraard zijn dat nogal flauwe, extreme voorbeelden, maar ik heb wel eens gelezen dat zo af en toe berekeningen in de praktijk wel degelijk worden verstoord door kosmische straling (al ging dat geloof ik meer om bits opgeslagen in het werkgeheugen dan om de logische modules in een chip).

Ik heb geen flauw idee hoe groot de kansen zijn dat rekenstappen mis gaan, maar zelfs als we dat punt bereiken dan kunnen we altijd foutencorrectie algoritmes gebruiken om dat weer tegen te gaan, bijvoorbeeld door iedere berekening meerdere keren te herhalen.

Gebruikersavatar
Berichten: 4.216

Re: Grenzen aan de complexiteit?

Ik vraag mij af of of je zo'n grens dan nog wel wezenlijk kunt verleggen door nog meer rekenstappen te maken.

Overigens gaat het mij om fouten die onafhankelijk per module gemaakt worden, dus niet om blikseminslag e.d. waarbij de oorzaak van de fouten bekend en direct waarneembaar is.

Gebruikersavatar
Berichten: 1.762

Re: Grenzen aan de complexiteit?

Je kunt ook bijvoorbeeld drie poorten gebruiken in plaats van eentje en uitgaan van wat de meerderheid beslist.
De foutkans verandert dan van 1-b naar circa 3.(1-b)^2.
Daarin is niet meegerekend de logica die die meerderheid 'waarneemt; die zal natuurlijk ook niet perfect zijn..

Gebruikersavatar
Berichten: 1.762

Re: Grenzen aan de complexiteit?

Bij een lange en complexe berekening is het misschien nog wel eenvoudiger.
De fout zal niet steeds bij dezelfde poort optreden (anders is die poort gewoon defect).
Dan zal, in het algemeen, iedere fout tot een ander antwoord leiden.

Doe je de berekening 10 maal en krijg je drie gelijke antwoorden en zeven die anders zijn en ook onderling verschillend, dan kun je er vanuit gaan dat die drie gelijke antwoorden correct zijn.

Gebruikersavatar
Berichten: 2.627

Re: Grenzen aan de complexiteit?

Professor Puntje schreef:
do 10 okt 2019, 14:02
Ik vraag mij af of of je zo'n grens dan nog wel wezenlijk kunt verleggen door nog meer rekenstappen te maken.
Waarom niet?

Er vanuit gaande dat de kans op een fout onafhankelijk is van eerdere berekeningen kun je de berekening gewoon herhalen, of, zoals Xilvo aangeeft, meerdere keren parallel uitvoeren en zien wat de meerderheid zegt. Op die manier kun je de kans op een fout willekeurig klein maken. Dit principe wordt al op talloze andere terreinen toegepast, zoals bij telecommunicatie, of het uitlezen van CDs of DVDs.

Dit werkt natuurlijk niet als de fouten niet onafhankelijk van elkaar zijn, maar in dat geval is de chip gewoon defect en kun je hem vervangen.

Gebruikersavatar
Berichten: 4.216

Re: Grenzen aan de complexiteit?

Ik zal bekijken of ik een vereenvoudigd rekenvoorbeeld kan bedenken om te zien of het probleem op de aangegeven manier kan worden ondervangen.

Gebruikersavatar
Berichten: 458

Re: Grenzen aan de complexiteit?

Als je het per module bekijkt, is er geen probleem, één module kan onbeperkt foutloos 0 en 1 genereren,

het gaat pas fout als ze samen moeten werken, dan wordt timing en afstand een probleem,
als dat niet goed wordt afgestemd nemen de fout marges toe.

In de de tijd van deZ80 was een leuk experiment de klok snelheid van 4 Mhz naar 6 te brengen,
dat kon deze Z80 toen officieel niet aan, maar als je het deed was 2X2 ineens geen 4 meer maar 3,9
De processor bleef werken het crashte niet.

In big data wordt al rekening gehouden met ernstige entropie, op den duur is de data niet meer bruikbaar.


Gebruikersavatar
Berichten: 1.762

Re: Grenzen aan de complexiteit?

Ik weet niet of een processor zelf kan crashen maar als een processor fouten maakt crasht een computer binnen te kortste tijd.

Ik betwijfel of een computer in plaats van 4 3,9 geeft als antwoord op de opdracht '2x2'.
Dan werd sowieso wat software aan het werk gezet want een Z80 kan zelf niet vermenigvuldigen.

Gebruikersavatar
Berichten: 458

Re: Grenzen aan de complexiteit?

Ik was er zelf bij, en het staat je vrij om het wel of niet te geloven, ik kan daar verder niets mee.
Het moet een timings geval zijn geweest.

En met het andere ben ik het niet met je eens, software kan niets...
het is de processor die het werk doet, die heeft vermenigvuldig registers etc, laad de instructies zelf,

Software is niets namelijk, slechts een verzameling van eenen en nullen met geen enkele waarde zolang ze
geen relatie hebben met bepaalde hardware die het werk kan doen en de insstructie kan lezen.

Maar volgens mij gaan we nu over op een ander topic, en ik wil de TS niet verstoren

Gebruikersavatar
Berichten: 4.216

Re: Grenzen aan de complexiteit?

Laten we een extreem voorbeeld bekijken. We hebben een zeer complexe computer die door het grote aantal logische eenheden en de complexiteit van de draaiende programmatuur van de hier veronderstelde twee mogelijke uitkomsten 0 en 1 met een kans van 3/4 de juiste uitkomst oplevert en verder met een kans 1/4 de foute uitkomst vermeldt. We laten nu eenzelfde berekening door drie van zulke computers A, B en C uitrekenen waarbij we aannemen dat 1 de juist uitkomst is. Dan kunnen we met die drie computers bij toepassing van de meerderheidsregel precies de volgende gevallen onderscheiden:

A B C
0 0 0 => fout
0 0 1 => fout
0 1 0 => fout
0 1 1 => goed
1 0 0 => fout
1 0 1 => goed
1 1 0 => goed
1 1 1 => goed

Bij mijn kladberekening neemt de kans op een foute totaaluitkomst bij gebruik van drie computers en de meerderheidsregel zo inderdaad af.

Gebruikersavatar
Berichten: 1.762

Re: Grenzen aan de complexiteit?

Het leek me onwaarschijnlijk maar ik wil jouw waarneming niet in twijfel trekken - het is onvoorspelbaar wat een schakeling gaat doen als die fouten maakt dus dit behoort tot de mogelijkheden. Waarschijnlijk niet reproduceerbaar, vermoed ik?

Een Z80 kan uit zichzelf niet vermenigvuldigen, dat gebeurt echt in software. Het is gewoon een klein programmaatje dat de processor uitvoert om tot een vermenigvuldiging te komen.

Gebruikersavatar
Berichten: 458

Re: Grenzen aan de complexiteit?

@pp, dit is wat er gebeurt als je vervuilde data gebruikt, dan vervuild de output steeds erger.

Op dit moment bij BIG DATA analyses hebben ze daar erg veel last van, er wordt namelijk
geen data weg gegooid...alles ook rubish blijft bewaard.

@Xilvo, ik heb in de jaren 80 veel assembler geprogrammeerd, en wij keken daar toch anders tegen aan.
maar het is maar een mening.
Laatst gewijzigd door WillemB op do 10 okt 2019, 19:13, 1 keer totaal gewijzigd.

Gebruikersavatar
Berichten: 1.762

Re: Grenzen aan de complexiteit?

Met kansen erbij:

A B C
0 0 0 => fout 0,016
0 0 1 => fout 0,047
0 1 0 => fout 0,047
0 1 1 => goed 0,141
1 0 0 => fout 0,047
1 0 1 => goed 0,141
1 1 0 => goed 0,141
1 1 1 => goed 0,422

Kans op een fout resultaat is dan 0,156

Gebruikersavatar
Berichten: 1.762

Re: Grenzen aan de complexiteit?

WillemB schreef:
do 10 okt 2019, 19:13
@Xilvo, ik heb in de jaren 80 veel assembler geprogrammeerd, en wij keken daar toch anders tegen aan.
maar het is maar een mening.
Ik ook. Hoe je tegen software aankijkt is inderdaad een mening; dat vermenigvuldigen niet in de instructieset van de Z80 zat is een feit ;)

Reageer