NL192354C - Sorteerinrichting. - Google Patents

Description

Sorteerlnrichtlng

De uitvinding heeft betrekking op een inrichting voor het opnieuw rangschikken van gegevens in een gewenste volgorde, voorzien van ten minste een sorteermoduul voor het ontvangen van sequentieel 5 toegevoerde gegevens en een vergelijkingsschakeling in elk moduul, welke normaliter bestemd is om een volgorde te bepalen, waarin de gegevens worden afgeleverd door de waarden van paren gegevens met elkaar te vergelijken.

Een dergelijke inrichting is bekend uit het artikel ”A TDM switch based on sorting” door D. Maiwald et al in IEEE Int. Conf. on Communications, Seattle, Washington, 11-13 Juni 1973, vol. 2, bladzijden 39-24/39-10 27. In dit artikel is sprake van een ’’bubble-sort” of bellensorteerinrichting waarbij bovendien de te sorteren gegevens sleutelwaarden zijn met eraan toegevoegde registraties die in de volgorde van de sleutelwaarden gerangschikt moeten worden.

De essentie van bellensorteren is gelegen in de onderlinge verwisseling van twee naast elkaar gelegen gegevens in de hoeveelheid gegevens, welke wordt gesorteerd. Tijdens elke verwisseling worden de 15 waarden van de gegevens met elkaar vergeleken en worden de gegevens, indien nodig, opnieuw gerangschikt, teneinde deze in de voorafbepaalde relatie te brengen bijv. de kleinste eerst of de grootste eerst. De verwisselingen worden meer in het bijzonder sequentieel uitgevoerd, in het algemeen door alle gegevens in de hoeveelheid een aantal malen af te tasten of te doorlopen totdat geen verdere verwisselingen meer worden uitgevoerd, op welk moment de gehele hoeveelheid naar wens is gesorteerd. Vele van de methoden 20 van het bellentype zijn met "soft-ware” gerealiseerd en moeten derhalve in wezen worden beperkt tot een reeks sequentiële handelingen, aangezien de meeste rekeninrichtingen voor algemene doeleinden slechts een processor omvatten. Om dientengevolge optredende verwerkingssnelheidsbepetkingen te elimineren, zijn voor bellensorteren verschillende ”hard-ware’’-realisaties voorgesteld, waarbij gebruik wordt gemaakt van een conventionele ge'integreerde-ketentechnologie en magnetische bellendomeininrichtingen.

25 De doeltreffendheid van de bekende bellensorteerstelsels worden afgemeten tegen een groot aantal factoren, zoals het bereikbare rendement en de latentheid evenals de vereiste geheugenafmetingen. De beschouwde inrichting is beperkt in termen van het aantal gegevens, dat in elke hoeveelheid kan worden gesorteerd en het ontwerp is niet van toepassing op modulaire vervaardiging, waarbij gebruik wordt gemaakt van VLSI-technologie. Vele van de bekende sorteerinrichtingen, waarbij de werking met succes is 30 verbeterd in termen van sommige van de bovenstaande criteria, zijn desalniettemin duur of lastig te realiseren.

De problemen worden volgens de uitvinding opgelost, doordat wordt voorzien in een inrichting zoals boven omschreven, met het kenmerk, dat de moduul is voorzien van een detectieschakeling voor het detecteren van het feit of een van de sequentieel toegevoerde gegevens in het paar een bepaald afstands-35 gegeven is, en een eerste schakeling, die in responsie op het detecteren van het bepaalde afstandsgegeven het paar gegevens, inclusief het bepaalde afstandsgegeven, in dezelfde volgorde aflevert als die, waarin het paar gegevens door de moduul is ontvangen.

De uitvinding voorziet in een seriereeks van identieke sorteermodulen, die alle synchroon kunnen worden geklokt. De te sorteren gegevens treden op in hoeveelheden, waarbij elk gegeven meer in het bijzonder een 40 waarde heeft, welke de volgorde bepaalt waarin dit gegeven moet worden gerangschikt, vergeleken met andere gegevens in de hoeveelheid. Bij elke klokpuls wordt een gegeven aan de eerste moduul toegevoerd en elke moduul, welke twee gegevens bevat, vergelijkt de waarden van de gegevens en draagt een van de gegevens naar de volgende moduul over, afhankelijk van het gewenste type sortering. De gegevens kunnen numeriek, alfabetisch of overeenkomstig een andere voorafbepaalde relatie worden gesorteerd. Het 45 niet-doorgelaten gegeven wordt vastgehouden en bij de volgende vergelijking gebruikt.

Elke moduul is zodanig ingericht, dat deze een speciaal ’’afstands”-gegeven onderkent, dat aan een hoeveelheid te sorteren gegevens vooraf gaat of dat een hoeveelheid gegevens van de volgende scheidt. Wanneer een afstandsgegeven door de sorteermoduul wordt ontvangen, worden het afstandsgegeven en het andere gegeven, dat daarin aanwezig is, (bij de volgende twee klokpulsen) in dezelfde volgorde 50 afgeleverd als die, waarin zij werden ontvangen. Hierdoor kan een reeks van N-sorteermodulen, die op de bovenbeschreven wijze is uitgevoerd, op een doeltreffende wijze hoeveelheden van maximaal N-gegevens doeltreffend sorteren zolang als de gegevens in elke hoeveelheid door een afstandsgegeven zijn gescheiden. Dientengevolge wordt het rendement vergroot en is de inrichting meer flexibel dan een conventionele bellensorteerinrichting.

55 Een soortgelijk stelsel kan worden gebruikt voor het sorteren van registraties, welke informatie en een bijbehorende sleutel omvatten. Bij deze configuratie worden de sleutels aan de sorteermodulen toegevoerd, terwijl de overeenkomstige informatie door een reeks nevenmodulen aan een herrangschikking wordt onderworpen.

De sortering kan ook worden gebruikt voor het uitvoeren van permutaties, door de registratiesleutels op een gewenste wijze opnieuw worden gemerkt of gemanipuleerd. Als een voorbeeld kan de volgorde van een reeks gegevens naar de tijd worden omgekeerd door aan de gegevens sleutels in afnemende volgorde 5 toe te wijzen. Een sortering van deze registraties in toenemende sleutelvolgorde leidt dan tot de gegevens in de omgekeerde tijdvolgorde.

Een bepaalde toepassing is de verwisseling van tijdgleuven in een multiplex signaal met tijdverdeling. Zo kan bijv. elke tijdgleuf in een multiplex signaal met tijdverdeling worden beschouwd als het informatie-gedeelte van een registratie. Door met de informatie in elke tijdgleuf een sleutel te laten samenwerken, kan 10 de volgorde van de gleuven op een geschikte wijze worden verwisseld.

De uitvinding zal onderstaand nader worden toegelicht onder verwijzing naar de tekening. Daarbij tonen: figuren 1-3 de wijze waarop een reeks gegevens wordt gesorteerd onder gebruik van een bekende bellensorteermethode; 15 figuren 4-6 de wijze, waarop twee hoeveelheden gegevens worden veiwerkt onder gebruik van een verbeterde bellensortering; figuren 7 en 8 blokschema’s van verschillende uitvoeringsvormen van modulen, welke dienen voor het sorteren van registraties; figuren 9 een andere inrichting voor het uitvoeren van de afstandsdetectiefunctie bij de sorteermoduul 20 volgens figuur 8; figuren 10 een blokschema van een bekende tijdgleufverwisselinrichting; figuren 11 het gebruik van een seriereeks van registratiesorteermodulen, zoals die volgens figuur 7 of 8, voor het verwisselen van tijdgleuven van een multiplex signaal met tijdverdeling (TDM)-signaal en figuren 12 het gebruik van een reeks registratiesorteermodulen van het in figuur 7 of 8 afgebeelde type 25 voor het opnieuw rangschikken van lege tijdgleuven in een TDM-signaaf.

De figuren 1-3 tonen grafisch de begin-, midden- resp. eindcyclus van een conventionele bellensorteer-werking. In de drie figuren zijn voor dezelfde elementen dezelfde verwijzingen gebruikt. Zoals aangegeven in figuur 1 wordt aangenomen, dat een reeks van tien gegevens met numerieke waarden, 8, O, 1, 9, 7, 5, 3, 30 6, 4 en 8 moet worden gesorteerd en dat de gegevens op het tijdstip t=0 vooraf moeten worden gebracht in een schuifregister 110 met tien posities, welk schuifregister individuele opzamelplaatsen 101-1 tot en met 101-10 bezit. Bij elke volgende klokpuls φ op de lijn 102 wordt de inhoud van het register 101 over een positie naar rechts bewogen en wordt het op dat moment op de plaats 101-1 aanwezige gegeven toegevoerd aan de ingang van een seriereeks 111 van tien sorteermodulen 111-1 t/m 111-10.

35 Elke sorteermoduul is bestemd voor het opslaan van twee toegevoerde gegevens in opzamelelementen, welke schematisch zijn weergegeven als bovenste en onderste helften, en het vergelijken van de waarden van de opgeslagen gegevens om een gegeven afhankelijk van het gewenste type sortering te kiezen. In het hierna volgende voorbeeld zal een inrichting voor het verschaffen van een laagste naar hoogste volgorde worden beschreven. Elk moduul voert het gekozen gegeven aan de uitgang daarvan toe, welke uitgang met 40 de volgende sorteermoduul is gekoppeld of naar een verbruiksinrichting voert in het geval van de laatste moduul. Tegelijkertijd ontvangt elke moduul aan de ingang daarvan een volgend gegeven uit de voorafgaande moduul of in het geval van de eerste moduul uit het register 101. Meer in het bijzonder werken de modulen synchroon onder bestuur van klokpulsen φ uit een (niet afgebeelde) klokbron. De uitgang van de laatste moduul 111-10 is gekoppeld met een verbruiksinrichting, zoals een register 121, dat (evenals het 45 register 101) tien opzamelplaatsen 121-1 tot 121-10 bezit en door pulsen φ op de lijn 102 wordt geklokt.

Zoals aangegeven in figuur 1, worden alle sorteermodulen 111-1 t/m 111-10 op het tijdstip t=0 in werking gesteld en bevat elke moduul twee gegevens met "zeer kleine" waarden, gesymboliseerd door de letter ”s”. Per definitie is de waarde ”s” kleiner dan elke verwachte waarde in de hoeveelheid te sorteren gegevens. Het in werking stellen kan op een aantal verschillende wijzen geschieden en is bij de bekende stelsels nodig 50 om hierna te beschrijven redenen. Op het tijdstip t=0 is nadat een klokpuls φ aanwezig is geweest, de inhoud van het register 101 over een positie naar rechts verschoven en is het gegeven met de waarde ”8” uit de opzamelplaats 101-1 nu in de sorteermoduul 111-1 opgeslagen. Aangezien alle modulen 111-1 t/m 111-10 initieel gegevens met dezelfde waarde s bevatten voor het optreden van de eerste klokpuls, wordt de inhoud van een opzamelplaats (schematisch, de bovenste helft) in elke moduul verschoven en vult het 55 gegeven met de waarde ”8”, ontvangen uit de opzamelplaats 101-1, de lege opzamelplaats in de moduul 111-1 aan het eind van de eerste klokperiode. Het gegeven met de waarde ”s” uit de laatste sorteermoduul 111-10 moet buiten beschouwing worden gelaten, aangezien dit gegeven voor geen verdere nuttige functie 3 IW33<« dient.

Na het optreden van de volgende klokpuls (t=2) is de inhoud van het register 101 weer naar rechts verschoven en is het gegeven met de waarde ”0” uit de opzameiplaats 101-1 toegevoerd aan de sorteer-moduul 111-1. Aangezien de moduul 111-1 de waarden 8 en ”s" gelijktijdig vergelijkt voor de gegevens, die 5 gelijktijdig in de twee opzamelplaatsen daarvan zijn opgeslagen en het gegeven met de waarde ”s” naar de moduul 111-2 doorlaat, wordt het gegeven met de waarde ”0" aan de zojuist vrijgekomen plaats (onderhelft) van de moduul 111-1 toegevoerd. De resterende modulen werken alle op een soortgelijke wijze. Aangezien op het tijdstip t=2 alle andere modulen gegevens met de waarde ”s” bevatten, "rimpelen" deze gegevens in wezen door de lege plaatsen (bovenste helften) van de resterende modulen en wordt een tweede gegeven 10 met de waarde ”s” buiten beschouwing gelaten.

Het bovenstaande proces wordt bij elke volgende klokpuls φ herhaald. Na de derde klokpuls heeft een vergelijking plaatsgevonden in de moduul 111-1 tussen de sleutelwaarden (8 en 0) van de eerste twee ingangsgegevens. De ”0” is het kleinst en dit gegeven wordt aan de volgende moduul 111-2 van de reeks toegevoerd. Wanneer weer een klokpuls optreedt, wordt de ”0” met de waarde van ”s” in de moduul 111-2 15 vergeleken; zoals reeds is vermeld, is de waarde van ”s” het kleinst en wordt dit gegeven verschoven. Om het gemakkelijker te maken de plaats van het te verschuiven gegeven in de grafische voorstelling volgens figuur 1-3 te detecteren, is een hoek van de bovenste of onderste moduulhelft, welke het gegeven met de kleinste waarde (voor het toevoeren van de volgende puls φ) bevat, gearceerd.

Aan het eind van tien kiokpulsen is het register 101 geleegd en is de inhoud daarvan nu volledig 20 opgeslagen in de sorteermodulen 111-1 t/m 111-5, die elk twee gegevens opslaan. Het is nu van belang om later te beschrijven redenen te beginnen met het reinigen van de sorteermoduul-reeks van gegevens met "grote” waarden, aangegeven door het symbool ”L" welke groter zijn dan elke mogelijke waarde, die reeds in de sorteermodulen aanwezig is. Het invoeren van de gegevens met "grote" waarden (bij dit voorbeeld zijn er 20 nodig) kan op een eenvoudige wijze geschieden door gegevens met de gewenste grote waarden 25 aan het eind van elke hoeveelheid gegevens, welke men wenst te sorteren, aan te hangen of door een schakelaar 125 zodanig opnieuw in te stellen, dat gegevens met grote waarden, welke in een hulpregister 130 zijn opgeslagen, aan de sorteermoduulreeks worden toegevoerd, nadat de gegevens in elke hoeveelheid volledig aan de reeks zijn toegevoerd.

Voortgaande met hetzelfde voorbeeld, doch thans verwijzende naar figuur 2 is de na de 11d klokpuls 30 (t=11) het eerste gegeven met de waarde ”L” de sorteermoduul 111-1 binnengetreden. Wanneer 14 kiokpulsen aanwezig zijn geweest, blijkt uit figuur 2, dat de gegevens zich in de gewenste gesorteerde volgorde bevinden. De gegevens moeten evenwel door de resterende modulen worden verwerkt, aangezien N-modulen nodig zijn bij het sorteren van andere hoeveelheden van maximaal N-gegevens. Nadat 20 kiokpulsen aanwezig zijn geweest, zijn de gegevens gereed om de moduul 111-10 te verlaten. Ter illustratie 35 toont figuur 3 de invoer van gegevens uit de sorteermodulen aan het register 121 tijdens de volgende 10 perioden, zodat aan het eind van 30 kiokpulsen het register 121 is gevuld met de gegevens, die in de gewenste volgorde zijn gesorteerd, d.w.z. gegevens met de laagste waarden eerst. Gegevens met de waarde ”L” vullen nu alle 20 opzamelplaatsen in de sorteermodulen 111 -1 t/m 111 -10 en deze gegevens kunnen worden vervangen door gegevens met een waarde ”s” in voorbereiding voor het sorteren van de 40 volgende hoeveelheid.

Het doel van het verschaffen van initiële ”s”- en uiteindelijke "L”-voor- en achterwaarden bij de bekende belsorteerinrichtingen is het scheiden van gegevens in naast elkaar gelegen hoeveelheden, welke aan de seriereeks van sorteermodulen worden toegevoerd en het beletten, dat gegevens uit een hoeveelheid in de gegevens van een voorafgaande of volgende hoeveelheid binnendringen. Indien bijv. het eerste gegeven 45 met de waarde ”L” in plaats daarvan een waarde had, welke niet groter was dan de waarden van alle voorafgaande gegevens, zou het gegeven zich tussen sommige van de voorafgaande gegevens in de sorteermodulen voorwaarts bewegen in het interval tussen de 10de en 30ste kiokpulsen, waardoor een fout ontstaat. Op een soortgelijke wijze zouden indien het initiële gegeven met de waarde ”s” in plaats daarvan een waarde had, welke niet kleiner was dan de waarden van alle volgende gegevens, de gegevens met de 50 kleinste waarden sommige van de gegevens in de voorafgaande hoeveelheid inhalen, hetgeen weer resulteert tot een onjuiste sorteeruitgangsreeks. Interferentie tussen de hoeveelheden kan verder worden geïllustreerd door de tien gegevens te beschouwen, welke oorspronkelijk in het register 101 zijn opgeslagen, behorende bij twee gescheiden hoeveelheden, die resp. 4 en 6 gegevens omvatten, zonder een speciaal voorste ("s”-waarden) of achterste (”L”-waarden) gegeven voor scheiding. Nadat deze tien 55 gegevens (8-0-1-9 en 7-5-3-6-4^-8) zijn gesorteerd, is het gewenste resultaat 0-1-8-9 en 3-4-5-6-7-8. Aangezien het onderscheid tussen gegevens in verschillende hoeveelheden verloren is gegaan, is de eerste groep gegevens, welke werkelijk ontstaat, 0-1-3-4 en de tweede groep 5-6-7-8-8-9.

Het gebruik van speciale gegevens als de voorste en achterste gegevens voor elke hoeveelheid van n gegevens, kan de tijd, welke nodig is voor het sorteren van 2n tot 4n klokpulsen meer dan verdubbelen, aangezien de inleidende werking met gegevens met ”s”-waarden of het reinigen van de gegevens met ”L”-waarden elk in serie over een interval van 2n klokpulsen moet hebben plaatsgevonden. De overgang 5 vanuit gegevens met 2n eerdere ”L”-waarden naar de volgende groep van 2n gegevens met ”s”-waarden kan evenwel soms gelijktijdig in een klokperiode plaatsvinden; anders is nog een periode van 2n nodig. Het verlies aan verwerkingssnelheid, dat zich bij het beschreven inleidings/reinigingsproces voordoet, is op een relatieve basis nog ernstiger bij de conventionele met ’’hard-ware” gerealiseerde bellensorteerinrichtingen. Meer in het bijzonder wordt de reeks van sorteermodulen zolang gemaakt, dat de grootste hoeveelheid van 10 te sorteren gegevens kan worden verwerkt, waarbij N modulen aanwezig zijn voor een te verwachten maximale hoeveelheid van N-gegevens. Indien kleine hoeveelheden aanwezig zijn, moet desalniettemin de gehele sorteermoduulreeks worden geinitialiseerd en gereinigd onder gebruik van 2N speciale voorste/ achterste s en L-gegevens. In dit geval wordt bij de initialisering/reiniging meer tijd gebruikt dan voor de werkelijke sortering nodig is.

15 De moeilijkheden, welke zich tengevolge van het zojuist beschreven initialiserings/reinigingsproces voordoen, worden vermeden door het introduceren van een afstandsgegeven met een bepaalde waarde tussen elke hoeveelheid te sorteren gegevens, en door elke sorteermoduul gevoeliger te maken voor de aanwezigheid van het afstandsgegeven, hetgeen in figuur 4-6 grafisch is aangegeven met een ”x". Wanneer een afstandsgegeven door een moduul wordt gedetecteerd, levert deze moduul opgeslagen 20 gegevens in dezelfde volgorde als waarin zij werden toegevoerd, over de volgende twee klokpulsen. Door deze constructie wordt ervoor gezorgd, dat de gegevens uit elke hoeveelheid niet binnendringen in de gegevens van voorafgaande of volgende hoeveelheden. Ter illustratie wordt aangenomen, dat dezelfde tien gegevens met dezelfde waarden, gebruikt bij het voorbeeld volgens figuur 1-3, een eerste hoeveelheid met vier gegevens (8-0-1-9) en een tweede hoeveelheid van zes gegevens (7-5-3-6-4-8) vormen. De 25 hoeveelheden worden evenwel gescheiden door een extra afstandsgegeven of een bepaalde sleutel met een bepaalde waarde, gesymboliseerd door ”x” in figuur 4. Bij dit voorbeeld wordt aangenomen, dat de sorteermodulen 111-1 tot 111 -10 initieel gegevens met waarden "P" uit een of meer voorafgaande hoeveelheden bevatten en dat het meest recente ingangssignaal voor de moduul 111-1 een afstandsgegeven is, dat de voorafgaande hoeveelheid gegevens scheidt van de hoeveelheid, welke op het punt 30 staat te worden verwerkt, welke hoeveelheid de waarden 8-0-1-9 heeft en welke in de registerplaatsen 101-1 tot 101-4 zijn opgeslagen.

Na het optreden van de eerste klokpuls (t=1) is het voorafgaande gegeven, dat in een van de opzamel-plaatsen (onderste helft) van de sorteermoduul 111-1 is opgeslagen, naar de volgende moduul 111-2 verschoven en vervangen door het initiële gegeven met de waarde (8), opgeslagen op de opzamelplaats 35 101-1. Dit geschiedt omdat het door het ”x” symbool voorgestelde afstandsgegeven het laatste gegeven was, dat de moduul 111-1 binnentrad. Op het moment, dat het afstandsgegeven werd gedetecteerd, hield de moduul 11-1 dit gegeven vast en liet het andere opgeslagen gegeven door naar de volgende moduul. Om dezelfde reden bewoog na de tweede klokpuls (t=2) het afstandsgegeven zich naar de moduul 111-2, aangezien het gegeven dan niet het meest recente invoergegeven van de moduul 111-1 is. Na vier 40 klokpulsen, als aangegeven in figuur 4, zijn alle gegevens in de eerste hoeveelheid aanwezig in de sorteermodulen 111-1 en 111-2. Wanneer de volgende klokpuls optreedt, treedt het afstandsgegeven, dat de eerste hoeveelheid volgt en deze van de volgende hoeveelheid scheidt, de moduul 111-1 binnen.

De werking van de sorteermodulen in aanwezigheid van een afstandsgegeven, wordt verder geïllustreerd door de status van de modulen voor en na de 6de klokpuls te vergelijken. Het blijkt, dat het afstands-45 gegeven in de sorteermodulen 111-3 in dit interval naar de volgende moduul is bewogen, omdat dit gegeven reeds gedurende twee klokpulsen op zijn plaats was. Anderzijds is het afstandsgegeven in de moduul 111-1 niet bewogen, aangezien dit gegeven slechts bij de voorafgaande periode was ingevoerd en derhalve het meest recent ingevoerde gegeven was. Resumerende werken de beschreven sorteermodulen door de waarden van twee opgeslagen gegevens bij elke klokperiode te vergelijken en door een gegeven 50 aan de volgende moduul toe te voeren, afhankelijk van de relatie tussen de waarden van de gegevens. Normaliter worden de waarden van de gegevens hetzij numeriek, alfabetisch of overeenkomstig een andere gewenste relatie met elkaar vergeleken. Wanneer evenwel een afstandsgegeven met een bepaalde waarde wordt gedetecteerd, wordt dit gegeven op een speciale wijze behandeld en werkt de moduul anders. De keuze van een gegeven voor overdracht naar de volgende moduul is nu gebaseerd op de volgorde waarin 55 de gegevens aan deze moduul werden toegevoerd. Het oudste gegeven wordt aan de volgende modulen toegevoerd, onafhankelijk van de waarde van het gegeven, terwijl het meest recent toegevoerde gegeven in elke moduul gedurende een klokinterval wordt vastgehouden.

O I9M9·»

Voortgaande met een omschrijving van figuur 5, zijn nadat de 12de klokpuls aanwezig is geweest, de zes gegevens in de tweede hoeveelheid en het afstandsgegeven, dat deze hoeveelheid van weer een andere hoeveelheid scheidt, volledig aan de sorteermoduulreeks toegevoerd. Na deze hoeveelheid kunnen nog meer gegevens worden ingevoerd, doch voor dit doel van het voorbeeld omvatten die gegevens 5 gegevens, welke eenvoudig zijn aangeduid met het symbool "A”.

De weiking van de sorteerinrichting zet zich gedurende een aantal verdere perioden voort, totdat na de 20de periode (zie figuur 5) het initiële gegeven in de eerste hoeveelheid gereed is om uit de moduul 110-10 te worden afgevoerd. Uitgangsgegevens kunnen worden toegevoerd aan een opzamelregister of een andere verbruiksinrichting. Ter illustratie evenwel worden de gegevens in figuur 6 toegevoerd aan en verschoven in 10 een register 121. Het blijkt, dat na 30 klokpulsen de beide hoeveelheden gegevens op de juiste wijze zijn gesorteerd, zonder dat tijd verloren is gegaan, welke nodig was voor het initialiseren of reinigen van de sorteermodulen van speciale gegevens met de kleine (s) of grote (L) sleutels, nodig bij de bekende stelsels, waarvoor de in figuur 1-3 afgebeelde voorbeelden typerend zijn.

Een blokschema van een uitvoeringsvorm van een registratiesorteermoduul vindt men in figuur 7. In 15 wezen omvat elke registratiesorteermoduul een sorteerketen 700 voor het sorteren van sleutels, welke met elke registratie samenwerken op de zojuist beschreven wijze, en een nevenketen 750 voor het opnieuw rangschikken van de informatie van elke registratie in dezelfde volgorde als de overeenkomstige sleutel. De sorteerketen 700 ontvangt de bij elke registratie behorende sleutels en voert een sortering op de bovenbeschreven wijze uit en wel door de sleutels te vergelijken en een sleutel voor het uitgangssignaal te 20 kiezen, gebaseerd op de relatieve waarde of volgorde van invoer van de sleutels. De nevenketen 750 ontvangt de informatie voor de registratie met de overeenkomstige sleutel en kiest de informatie van een registratie als uitgangssignaal wanneer de overeenkomstige sleutel in de sorteerketen wordt gekozen.

Voor het uitvoeren van de sleutelsortering, wordt een bij een registratie behorende sleutel toegevoerd aan de lijn 740 en aan het ene of het andere van twee sleutel registers 701 of 702 bij het volgende optreden 25 van een klokpuls φ, die door een niet afgebeelde klokbron wordt opgewekt. Het bepaalde register van de registers, dat de sleutel ontvangt, hangt af van het feit, welke van de sleutels, opgeslagen in deze registers, werd gekozen voor toevoer aan de sorteerketen van de volgende moduul in de reeks. Deze keuze geschiedt normaliter door de waarden van de in registers 701 en 702 opgeslagen sleutels te vergelijken, welke resp. zijn aangeduid met "A” en "B” terwille van een meer gemakkelijke verdere toelichting. In het 30 geval evenwel, waarbij een van de opgeslagen sleutels een bepaalde waarde heeft, welke wordt onderkend als een afstandsgegeven, worden de waarden buiten beschouwing gelaten en worden de sleutels in dezelfde tijdvolgorde, waarin zij aan de registers 701 en 702 werden toegevoerd, afgevoerd. De keuze, gebaseerd op de sleutelwaarde, vindt plaats in een vergeiijkingsinrichting 703, welke ingangssignalen (bijv.

A en B) uit de beide registers 701, 702 ontvangt en op de lijn 707 een hoog uitgangssignaal levert indien A 35 < B wanneer het bijvoorbeeld gewenst is de gegevens in volgorde van de laagste naar de hoogste numerieke orde te sorteren. Indien de tegengestelde numerieke volgorde gewenst is, wordt de vergelrjkings-inrichting 703 op een eenvoudige wijze gemodificeerd voor het verschaffen van een hoog uitgangssignaal wanneer A > B.

Wanneer de in het register 701 opgeslagen sleutel (A) kleiner is dan de sleutel B in het register 702, 40 wordt het hoge uitgangssignaal van de vergeiijkingsinrichting 703 via de EN-poort 711 en de OF-poort 712 aan de inschakelingang 721 van het register 701 toegevoerd, waardoor de op dat moment opgeslagen sleutel (A) aan de lijn 731 wordt toegevoerd, terwijl de nieuwe sleutel (op de ingangslijn 740) aan het register wordt toegevoerd. Een omkering van het hoge uitgangssignaal van de OF-poort 712 onder gebruik van de omkeerinrichting 716 zorgt ervoor, dat de inschakelingang 722 van het register 702 niet wordt 45 geactiveerd wanneer A < B. De sleutel A wordt aan de uitgang 710 van de sorteerketen 700 toegevoerd via een multiplex schakelaar 705, welke uit de OF-poort 712 ook een positiebesturingsingangssignaal ontvangt. Zoals aangegeven in figuur 7, voert de schakelaar 705 de waarde A aan de uitgang 710 toe, wanneer de uitgang van de OF-poort 712 hoog is. Wanneer daarentegen de sleutel in het register 701 groter is dan de sleutel in het register 702 (A > B) dan zijn de uitgangssignalen van de EN-poort 711 en de OF-poort 712 50 laag, waardoor de invertor 716 het mogelijk maakt, dat het register 702 (via de lijn 722) de daarin opgeslagen sleutel aan de schakelaar 705 toevoert en de volgende sleutel uit de lijn 740 accepteert. De sleutel B wordt via de opnieuw ingestelde schakelaar 705 aan de uitgang 710 toegevoerd.

De sorteerketen volgens figuur 7 omvat ook een afstandsgegevendetector 704, welke ingangssignalen uit de beide registers 701 en 702 ontvangt en de aanwezigheid van een bepaalde afstandsgegevenwaarde in 55 een opzamelplaats controleert. Bij detectie wordt het uitgangssignaal van de detector hoog, waardoor de EN-poort 711 via de invertor 714 buiten werking wordt gesteld en de EN-poort 713 in werking wordt gesteld, teneinde een uit de geïnverteerde (Q)uitgang van een flip-flop 706 afkomstig signaal aan de OF-poort 712 toe te voeren. De flip-flop 706 dient als een geheugen van een bit, doordat deze flip-flop het uitgangssignaal van de OF-poort 712 op de informatie (D) ingang daarvan ontvangt en deze waarde opslaat, totdat de volgende klokpuls φ aan een klokingang wordt toegevoerd. Indien bijv. het afstandsgegeven de meest recente invoer voor het register 701 was, veroorzaakt het hoge uitgangssignaal van de OF-poort 712, welke 5 deze invoer heeft toegestaan, dat de Q-uitgang van de flip-flop 706 laag is en dit zorgt er op zijn beurt voor, dat de uitgangssignalen van de EN-poort 713 en de OF-poort 712 laag zijn, wanneer de volgende klokpuls optreedt. Dientengevolge komt het volgende gegeven, dat aan een multiplexinrichting 705 wordt toegevoerd, dan uit het register 702, onafhankelijk van een waardevergelijking. Aangezien het afstandsgegeven in het register 701 blijft, blijft het uitgangssignaal van de detector 704 hoog, waardoor de EN-poort 713 bij het 10 begin van de volgende periode ingeschakeld blijft. Het lage uitgangssignaal van de OF-poort 712 echter veroorzaakt nu, dat de Q-uitgang van de flip-flop hoog is bij de volgende klokpuls φ. De resulterende hoge uitgangssignalen van de EN-poort 713 en de OD-poort 712 veroorzaken, dat de afstandssleutel uit het register 701 wordt gevoerd, waardoor de gewenste werking met twee perioden wordt voltooid. Resumerende kiest bij het normale bedrijf de sorteeiketen 700 een sleutel voor toevoer aan de volgende moduul, 15 als functie van de relatieve waarden van de sleutels. Na detectie van een afstandsgegeven echter, worden de sleutels in de sorteermoduul uitgelezen in dezelfde volgorde als die, waarin zij werden toegevoerd.

Elk van de registratiesorteermodulen 111-1 t/m 111-10 van de figuren 4-6 omvat ook nevenketens, zoals de keten 750 van figuur 7, welke de informatie van elke registratie in dezelfde volgorde rangschikken als de overeenkomstige sleutel, die bij die registratie behoort. Voor dit doel omvat de keten 750 informatieregisters 20 751 en 752, die elk in staat zijn de informatie van een registratie, ontvangen op de informatieingang 760, op te slaan. Het uitgangssignaal van de OF-poort 712, dat het register 701 direct in werking stelt, en het register 702 via de omkeerinrichting 716 in werking stelt, voert ook inschakelingsingangssignalen direct aan het register 751 via de omkeerinrichting 756 aan het register 752 toe. Door deze registers met de registers in de sorteerketen 700 te koppelen, kan informatie bij het optreden van een klokpuls φ aan het juiste register 25 worden toegevoerd. De nevenketen 750 omvat ook een multiplex schakelaar 755, welke identiek is aan de multiplex inrichting 705, welke eveneens op het uitgangssignaal van de OF-poort 712 reageert, zodat uitgangsinformatie van het gekozen register 751 of 752 aan de informatieuitgang 770 wordt toegevoerd.

De vakman kan verschillende wijzigingen in het sorteermoduulstelsel volgens de uitvinding aanbrengen, afhankelijk van de aard van de gegevens, welke worden gesorteerd. Normaliter bestaan de gegevens uit 30 woorden met een aantal bits en een tekenbit, die parallel aan de registers 701 en 702 worden toegevoerd, en de vergelijkingsinrichting 702 dient om de waarden, rekening houdende met de tekenbits, numeriek met elkaar te vergelijken. Het kan evenwel gewenst zijn in sommige gevallen alleen op absolute waarde te sorteren. De gegevens kunnen ook bestaan uit woorden, die alfabetisch worden gesorteerd, of alfanumerieke symbolen, die volgens een andere voorafbepaalde relatie worden gesorteerd. Het afstandsgegeven 35 kan een bepaald woord (gewoonlijk uit een aantal bits bestaand woord) zijn, dat voor het betreffende doel is gereserveerd en de detector 704 kan een logische keten zijn, welke bestemd is om elk ingangssignaal met een vooraf opgeslagen versie van het afstandsgegeven te vergelijken. Wanneer registraties worden gesorteerd, kunnen de registers 751 en 752 groter zijn dan de registers 701 en 702, afhankelijk van de hoeveelheid informatie, welke zij bevatten.

40 Een andere uitvoeringsvorm van een registratiesorteermoduul is weergegeven in figuur 8. Evenals de zojuist beschreven inrichting zijn een sorteerketen 800 en een nevenketen 850 aanwezig voor het resp. sorteren van de sleutels en de overeenkomstige informatie in hoeveelheden registraties. De sorteerketen 800 omvat eerste en tweede sleutelopzamelregisters 801 en 802, doch elke sleutel, die aan de ingangslijn 840 wordt toegevoerd, wordt steeds bij elke klokpuls φ aan het eerste register 801 toegevoerd. De sleutels, 45 die in de registers 801 en 802 zijn opgeslagen, worden met elkaar vergeleken in een vergelijkingsinrichting 803, welke een hoog uitgangssignaal levert, indien de waarde (A) genoemd in het register 801 de waarde (B genoemd) in het register 802 overschrijdt, aannemende, dat een numerieke sortering van de laagste tot de hoogste orde gewenst is. Voor een sortering van de hoogste naar de laagste orde wordt het uitgangssignaal van de vergelijkingsinrichting 803 hoog, wanneer A < B.

50 Indien het uitgangssignaal van de vergelijkingsinrichting 803 hoog is, stelt het resulterende hoge uitgangssignaal van de OF-poort 806 een multiplex inrichting 805 zodanig in, dat de in het register 802 opgeslagen sleutel aan de uitgangslijn 810 wordt toegevoerd. De EN-poort 807 wordt in werking gesteld, om een klokpuls φ naar het register 802 door te laten, zodat de opgeslagen sleutel daarvan in wezen wordt afgevoerd en wordt vervangen door de sleutel, die in het register 801 is opgeslagen. Indien daarentegen het 55 uitgangssignaal van de vergelijkingsinrichting 803 laag is, is het uitgangssignaal van de OF-poort 806 ook laag, mits geen afstandsgegeven wordt gedetecteerd. In dit geval wordt de schakelaar 805 opnieuw ingesteld om de in het register 801 opgeslagen sleutel (A) direct aan een multiplexinrichting 805 toe te voeren. De EN-poort 807 wordt op dit moment buiten werking gesteld, zodat de sleutel in het register 802 niet wordt gestoord. Resumerende vergelijkt de sorteerketen 800 de waarde van elke in het register 801 opgeslagen sleutel met de waarde van het eerdere in het register 802 opgeslagen sleutelingangssignaal. Indien aan een bepaalde vooraf gedefinieerde relatie wordt voldaan (bijv. het recente ingangssignaal is 5 kleiner dan het eerdere ingangssignaal), wordt de nieuw ontvangen sleutel aan de uitgang 810 van de sorteerketen toegevoerd. Indien niet aan de relatie wordt voldaan (bijv. het recente ingangssignaal is groter), dan wordt de eerder ontvangen sleutel in het register 802 toegevoerd aan de uitgang 810 en door het recente ingangssignaal vervangen. Voor het detecteren van een bepaalde sleutel voor een afstandsgegeven, omvat de keten volgens figuur 8 afstandsdetectoren 804a en 804b, die de inhoud van de resp.

10 registers 801 en 802 controleren. Indien een afstandsgegeven wordt gedetecteerd, wordt het hoge uitgangssignaal van de detector 804a en 804b via de OF-poort 806 gevoerd, om ervoor te zorgen, dat de multiplex inrichting 805 in de in figuur 8 aangegeven positie blijft. Onder deze omstandigheden wordt de in het register 802 voor de langere tijd opgeslagen sleutel afgevoerd en wordt de bij het afstandsgegeven behorende sleutel naar het register 802 overgedragen en bij het volgende optreden van een klokpuls φ 15 afgeleverd. De orde van de sleutel blijft derhalve, zoals gewenst, behouden, wanneer een afstandssleutel wordt gedetecteerd.

Evenals de inrichting volgens figuur 7 omvat de inrichting volgens figuur 8 een nevenketen 850, welke informatie of registraties voor elk gegeven sorteert, overeenkomstig de bij dat geheugen behorende sleutel. De keten 850 omvat eerste en tweede informatieregisters 851 en 852, waarbij het register 851 een 20 ingangswoord uit de lijn 860 ontvangt en de inhoud daarvan via de multiplex inrichting 855 aan de uitgangslijn 870 toevoert, wanneer A < B en de schakelaar 855 zich in de neerwaartse stand bevindt. Wanneer A > B of wanneer een afstandssleutel wordt gedetecteerd, is het uitgangssignaal van de OF-poort 806 hoog, bevindt de multiplex inrichting 855 zich in de op-positie, als aangegeven in figuur 8, en wordt de in het register 852 vastgehouden informatie afgevoerd en vervangen door de informatie in het register 851 25 wanneer een klokwerking via de EN-poort 857 plaatsvindt.

Een gedeelte van de in figuur 8 afgebeelde sorteermoduulketen kan worden gewijzigd, als aangegeven in figuur 9, door de afstandsdetector 804b te vervangen door een vertragingsketen 901, welke bestemd is om het uitgangssignaal van de detector 804a te ontvangen en bij de volgende klokpuls φ een hoog uitgangssignaal te leveren. Bij deze vereenvoudiging is rekening gehouden met het feit, dat wanneer een 30 afstandssleutel in het register 801 wordt gedetecteerd (door de detector 804a) deze in het register 802 steeds een klokperiode later zal worden gedetecteerd (door de detector 804b).

De zojuist beschreven sorteerinrichting en sorteermethode vindt velerlei toepassing, zoals bij een tijdgleufverwisselinrichting, welke de volgorde van een reeks multiplexinformatiesignalen met tijdverdeling opnieuw kan rangschikken. In figuur 10 is een traditionele tijdgleufverwisselinrichting (uitwisselinrichting)

35 afgebeeld. Informatie in een reeks tijdgleuven 1000 wordt sequentieel toegevoerd aan een dubbel gebufferd geheugen, voorzien van de buffers 1001 en 1002. Wanneer een van de buffers wordt gevoed, wordt informatie uit de andere verwerkt. Op een soortgelijke wijze zijn de buffers 1005 en 1006 georganiseerd als een dubbele buffer, zodat wanneer de buffer 1006 wordt uitgelezen, de buffer 1005 wordt geregistreerd en omgekeerd. Er is een geheugen 1004 aanwezig om een processoreenheid 1003 ten aanzien van de 40 gewenste verwisselingen te instrueren; zo kan bijv. informatie, welke oorspronkelijk in de tijdgleuf E

aanwezig is, bestemd worden voor de tijdgleuf B enz. De processoreenheid 1003 neemt dan de informatie in de tijdgleuf E uit de buffer 1001 of 1002 vast en brengt deze in de buffer 1005 of 1006 op een plaats, overeenkomende met de gleuf B. Nadat de informatie uit alle tijdgleuven, opgeslagen in de buffer 1001 of 1002, na de buffer 1005 of 1006 is overgedragen, is de gewenste tijdgleufreeks 1007 verkregen. Deze 45 bekende uitwisselingsmethode vereist evenwel grote hoeveelheid (hardware) en een betrekkelijk lange behandelingstijd; elke tijdgleufuitwisseling vereist een uitlezing uit een geheugen, een uitlezing uit een buffer en een registratie in een buffer. Derhalve vereisen N tijdgleuven 3N perioden voor behandeling. Dientengevolge kunnen de ingangs- en uitgangsbuffers slechts elke 3N perioden worden uitgewisseld. De totale latentie van een dergelijke tijdgleuf-uitwisselinrichting bedraagt 9N perioden. Een nieuwe tijdgleuf kan elke 50 drie perioden aan de tijdgleufuitwisselinrichting worden toegevoerd.

Een tijdgleufverwisselinrichting, waarbij de behandelingstijd in sterke mate wordt verbeterd is in figuur 11 in blokschemavorm weergegeven. De verwisselinrichting kan worden gerealiseerd onder gebruik van de registratiesorteermodulen, als aangegeven in de figuren 7 of 8. Bij deze inrichting bestaat de te sorteren informatie uit de inhoud van de tijdgleuven in elk raster van een multiplex signaal met tijdsverdeling. Aan de 55 informatie worden bijbehorende sleutels toegevoegd door een sleuteltoewijsinrichting 1104 om de gewenste tijdgleufposities aan te geven. Zo wordt informatie in een raster met vijf tijdgleuven A-E, aangegeven in figuur 11, op de lijn 1101 gebracht en aan een register 1102 toegevoerd in de ontvangen volgorde (D-B-E-C-A). Om de volgorde van de tijdgleuven te permuteren in een gewenste volgorde, zoals bijvoorbeeld (C-A-D-E-B), associeert de sleuteltoewijsinrichting 1104 een sleutel met elke tijdgleuf. Bij het voorbeeld volgens figuur 11 wordt, aangezien het gewenst is informatie in gleuf C vanuit de vierde naar de eerste positie te bewegen, aan de eerste een sleutel met een waarde ”1” toegewezen. Op een soortgelijke 5 wijze moet de informatie in de gleuf B vanuit de tweede naar de vijfde positie worden bewogen, zodat daaraan een sleutel met een waarde ”5” wordt toegewezen. Aan het raster, bestaande uit vijf registraties, wordt vooraf een bepaalde ”afstands”-sleutel 1103 verhecht door een afstand sgonerator 1105.

De tijdgleufverwisseling geschiedt door de registraties (sleutels en informatie) toe te voeren aan een seriereeks van N-registratiemodulen 1120-1,1120-2, ...1120-N, welke, zoals reeds eerder is opgemerkt, kan 10 zijn uitgevoerd als de inrichting volgens figuur 7 of 8 en een sorteerketen en een nevenketen omvat. De sleutels worden gesorteerd wanneer zij vanuit de sorteerketen in een moduul naar de sorteerketen in de volgende moduul worden overgedragen, terwijl de informatie in de overeenkomstige volgorde door de nevenketens aan een herrangschikking wordt onderworpen. De waarde van N wordt zodanig gekozen, dat deze gelijk is aan de langste te verwachten hoeveelheid registraties (in dit geval, vijf gleuven). Het 15 uitgangssignaal van de laatste sorteerketen in de reeks van modulen is de oorspronkelijke informatie, die in de gewenste volgorde is gesorteerd. Deze informatie kan worden toegevoerd aan een register 1110, of, indien gewenst, aan een verdere behandelingsschakeling, waarbij de sleutels buiten beschouwing worden gelaten.

Tijdgleufverwisseling, onder gebruik van een sortering, zoals deze zojuist is beschreven, heeft een 20 latentie van 3N, hetgeen betekent, dat informatie van maximaal drie voorafgaande rasters moet worden verwerkt, voordat informatie voor het huidige raster wordt afgevoerd, en een nieuwe tijdgleuf bij elke periode kan worden verwerkt. Dit leidt tot een reductie in latentie met een factor 3 en een toename van de doorvoersnelheid met een factor 3 ten opzichte van de in figuur 10 afgebeelde traditionele tijdgleufverwissel-inrichting.

25 Een reeks registratiesorteermodulen van het in figuur 7 of 8 afgebeelde type kan ook worden gebruikt voor het opnieuw rangschikken van tijdgleuven in elk raster van een multiplexsignaal met tijdverdeling om gebruik te kunnen maken van lege tijdgleuven.

De rasters 1201 en 1211 bevatten tijdgleuven van een eerste en een tweede multiplex signaal met tijdverdeling. De sleutels 1 t/m M worden toegewezen aan de M gleuven in elk raster, een en ander 30 zodanig, dat de rasters na herrangschikking kunnen worden versmolten. Meer in het bijzonder worden de sleutels voor gevulde tijdgleuven in een signaal op een bepaalde wijze gekozen uit de sleutels, welke zijn toegewezen aan lege tijdgleuven in het andere signaal. De bij de resterende tijdgleuven in elk raster behorende sleutels worden, als gewenst, toegewezen uit de resterende ongebruikte sleutels van de oorspronkelijke M sleutels. De sleutels, welke aan elk raster worden toegewezen, worden dan afzonderlijk 35 gesorteerd en de bijbehorende tijdgleufinformatie wordt op een overeenkomstige wijze aan een herrangschikking onderworpen. Nieuwe rasters, die op deze wijze worden gevormd, kunnen worden versmolten voor het verkrijgen van een uiteindelijke reeks met minder lege tijdgleuven. Deze methode kan worden toegepast zolang als het totale aantal gevulde gleuven in beide rasters kleiner is dan het aantal gleuven in elk raster. Bij het in figuur 12 aangegeven voorbeeld, zijn aan de lege gleuven 1,3 en 4 in het raster 1201 40 de sleutels 1,3 en 5 toegewezen, terwijl aan de gevulde gleuven 1,2 en 3 van het raster 1211 sleutels zijn toegewezen, die op een bepaalde wijze worden gekozen uit hetzelfde stel (1,3 en 5), dat is toegewezen aan de lege gleuven in het raster 1201. De resterende sleutels worden toegewezen aan resterende gleuven in de rasters 1201 en 1211 in de bij wijze van voorbeeld gekozen reeksen 1202, 1212.

De op deze wijze gevormde registraties (sleutels plus tijdgleufinformatie) worden afzonderlijk gerang-45 schikt door registratiesorteermodulen 1203 en 1213, welke nieuwe rasters 1204 resp. 1214 verschaffen. Deze rasters kunnen via de multiplexinrichting 1220 of een andere soortgelijke combinatieinrichting worden versmolten voor het verkrijgen van een gecombineerd uitgangsraster 1230, dat bij voorkeur geen excessieve lege tijdgleuven omvat.

Het beschreven sorteermoduulstelsel kan op een eenvoudige wijze worden gerealiseerd onder gebruik 50 van VLSI-technologie en de modulariteit van het ontwerp maakt talrijke doeltreffende toepassingen mogelijk.

Ofschoon de sorteermodulen zijn aangegeven als modulen, die klokpulsen uit een enkele klokbron ontvangen, is het mogelijk de modulen ten aanzien van de tempering in serie met elkaar te verbinden, zodat elke moduul een tempeerpuls uit de voorafgaande moduul ontvangt. Voorts is het duidelijk, dat sorteren en permitteren betrekkelijk sterk aan elkaar gelijk zijn en dat een sorteerreeks kan worden gebruikt voor het 55 uitvoeren van permutaties, eenvoudig door de waarden van de sleutels opnieuw te merken.

Claims (1)

1. 9 > 9C«Mn Inrichting voor het opnieuw rangschikken van gegevens in een gewenste volgorde, voorzien van ten minste een sorteeimoduul, welke sequentieel toegevoerde gegevens ontvangt, en een vergelijkingsschakeling in 5 elke moduul, welke normaliter bestemd is voor het bepalen van een volgorde voor het afleveren van gegevens door de waarden van paren gegevens met elkaar te vergelijken, met het kenmerk, dat de moduul is voorzien van een detectieschakeling (704) voor het detecteren van het feit of een van de sequentieel toegevoerde gegevens in het paar een bepaald afstandsgegeven is, en een eerste schakeling (711-714, 705), die in responsie op het detecteren van het bepaalde afstandsgegeven het paar gegevens, inclusief het 10 bepaalde afstandsgegeven, in dezelfde volgorde aflevert als die, waarin het paar gegevens door de moduul is ontvangen. Hierbij 10 bladen tekening v