CA2160504C - Programmable pcm/tdm demultiplexer - Google Patents

Abstract

A programmable PCM/TDM demultiplexer including an FA
function unit including Frame Alignment Logic (FAL) hardware controlled by a Programmable Frame Alignment Controller (PFAC), and accompanied by a DECommutation and dejustification (DEC) function unit including Output Logic Hardware (OLH) controlled by a Programmable Decommutator Sequencer (PDS) controlled in turn by a Programmable Decommutator Sequencer Controller (PDSC).

Description

~1605~1 1 Specification 3 "Programmable PCM/TDM DeMultiplexer"

BACRGROUND OF THE INVENTION
6 Technical Field 7 The present invention relates generally to Pulse Code 8 Modulated/Time Division Multiplexed data communications 9 apparatus and more particularly to an improved means for accomplishing high frequency demultiplexing.

12 Discussion of the Prior Art 13 Fig. 1 represents individual electronic data sources Ia, 14 Ib, Ic,... timed by local oscillators (CLKa), (CLKb), (CLKc) and transmitting Pulse Code Modulated (PCM) data signals at 16 input rates RATEa, RATEb, RATEc, via Input Tributaries (ITa, 17 ITb, ITc) to inputs of a conventional Time Division 18 MUltipleXer (TDM MUX). TDM MUX, driven by its transmitter-19 oscillator Master CloCK (MCLK), samples the tributaries in some selected order at a rate faster than the total allowed 21 input rate and, as higher frequency-translated data bit 22 signals, multiplexes then into time-slots of a PCM/TDM signal 23 stream. This stream is then received and de-multiplexed by 24 PCM/TDM demultiplexer TDM DEMUX, which produces individual output data streams on output tributaries OTa, OTb, and OTc, 26 to output devices Oa, Ob, and Oc. Clock recovery unit CLKR

2260~~4 ,~.
. ~.
S
1 derives the Bit CLocK signal (BCLK) from the PCM/TDM signal 2 stream for use by the TDM DEMUX. After clock recovery has been 3 performed, the demultiplexing process involves the additional 4 steps of frame alignment, dejustification, and decommutation.
6 Frame A1 ictnment 7 Fig. 2 shows an example PCM/TDM signal stream of data 8 bits (Da), (Db), (Dc) grouped in octets during frame-9 intervals. Frame interval formats are defined conventionally by Frame Alignment (FA) and Multi-Frame Alignment (MFA) words 11 composed of patterns of Frame alignment bits (F) inserted 12 either contiguous to or periodically between frame boundaries.
13 When a PCM/TDM signal stream is received, in order for the 14 bits combined in the stream to be sorted out by the inverse process of demultiplexing, first, the MCLK timing is recovered 16 as the re-named BCLK signal. Then, bits comprising FA words 17 are searched in streams of bits assembled by a demultiplexer.
18 Candidate FA word patterns are compared against reference FA
19 word patterns until one matches. Unless bits which coincidentally mimic FA words distract the search, contiguous 21 F bit pattern-synch is achieved in one frame interval.
22 More generally, bits F can be interspersed along frames 23 as illustrated in Fig. 3. In this case, frame-synch requires 24 assembling candidate bits starting from every possible position for a FA word in a frame or multi-frame.

216Q~~~~
1 Assembling a candidate FA word from just one starting bit 2 position in each BCLK cycle may not achieve frame-3 synchronization until assembling candidate FA Words from bits 4 at every possible starting position. The probability of attaining frame synchronization is proportional to the total 6 possible starting positions from which FA candidate bits are 7 tested during a given cycle. This requires memory capacity 8 for the corresponding number of candidate FA pattern words.
9 Multiframe boundaries are coincident with frame boundaries. After FA synchronization there is only one ll possible starting position in each frame for a candidate Multi 12 Frame (MF) bit. In the absence of bit-errors, MF
13 synchronization is achieved afterwards within one more MF
14 interval.
16 Justification 17 In plesiochronous communications, signals from Ia, Ib, Ic 18 timed by CLKa, etc. having precision to prescribed tolerances 19 within which they are uncertain. Therefore, input tributary signal timing deviations are preferably accommodated by 21 Justification (J) bit time-slots (Fig. 3) during which 22 compensating bits may be inserted or deleted. Justification 23 Control (JC) words bit values indicate justification actions 24 to be taken. Each justifiable tributary needs a JC word and a J bit time slot. TDM groupings of frames in multi-frames 26 permits a common control word to be used to justify a 21605~~
._ .~.
,. , 1 different tributary in each frame. This way, a JC word will 2 not have to be tested for every tributary in every frame.
3 In positive justification, the PCM/TDM stream bit-clock 4 exceeds the nominal tributary bit-clock rates. Occasionally no source data bit is available to occupy a data-slot and so 6 the multiplexer transmits a "stuff" bit in the J bit time 7 slot, and also sets the Justification Control (JC) bits active 8 for the corresponding tributary.
9 Negative justification may be used where tributary bit-clock rates can exceed the nominal rate of the PCM/TDM stream.
11 J bit time-slots are initially vacant and occasionally used to 12 carry excess bits input from faster tributaries. In this case 13 the corresponding Justification Control bits are activated.
14 Positive/zero/negative justification uses both positive and negative J slots, and either adjusts up, down, or not at 16 all, rates of data bits received from input tributaries.
17 Bits JC are arranged either consecutively or interspersed 18 through frames to form JC words. JC words are conventionally 19 interpreted either by odd-majority bit-voting or by pattern-matching. When positive justified tributary frames are 21 received and active bits JC words are detected, stuff bits are 22 deleted from J slots. When negative-justified streams are 23 received and active JC words are detected, data bits are 24 retained in slots J. Zero de-justification deletes stuff bits from positive slots J and retains data bits in negative slots 26 J.

_ .~
1 Decommutation 2 Once the data stream has been dejustified, the bits are 3 routed to the appropriate tributary in accordance with the 4 format in which they were sampled in the multiplexer.
6 Prior Art Features and Performance 7 The prior art MPX-100 demultiplexer has been implemented 8 in an IC with a field-programmable working memory, using down-9 loaded software, for decommutating TDM formats in general.
The MPX-100-working memory is required to cycle at the rate 11 BCLK of the multiplexed stream. Any programmable 12 demultiplexer depending upon a programmable working memory to 13 cycle at the BCLK rate encounters a dilemma for an 14 implementation in ICs. Memory speeds are inversely related to their sizes. IC memory capacities must be balanced against 16 access speeds. This compromises functioning and programming 17 advantages. With its memory size, the MPX-100 has not 18 operated at 50 Mbit/sec.
19 Specific applications desire a small demultiplexer capable of very high-speed decommutation of TDM signals and 21 re-programmable for practically any TDM format.
22 U.S. patent No. 4, 377,861 by Huffman describes a 23 demultiplexer for re-distributing data bits to respective 24 tributaries by using individual channel units provided with real-time framing information by a state controller and 26 provided with tributary routing selectability by a 2160~0~
~- _ 1 microprocessor.
2 In U.S. patent No. 4,430,734 by Hubbard, multiple digital 3 voice channels are demultiplexed and added together to 4 establish conference calls. Voice channel data is stored in a buffer memory and extracted by a microprocessor.
6 There remains, therefore, an need for a programmable 7 decommutator capability to decommutate data streams, such as 8 tributaries in a telecommunications application, from a large 9 variety of TDM formats which operates at the highest attainable data rate and can be implemented in current state 11 of the art IC technology.

13 SUr'~IARY OF THE INVENTION
14 The.present invention provides a PCM/TDM demultiplexer which is both operable with fast input bit clocks and is re-16 programmable for a variety of formats and levels of 17 hierarchical demultiplexing. The invention is suitable for 18 embodiment in as few as two and preferable only one IC(s).
19 Memory sizes and access delay times are minimized by separating demultiplexing transformations into a separate FA
21 function unit and a DECommutation and dejustification (DEC) 22 function unit which operate in a coordinated manner.
23 Memory sizes and access delay times are further minimized 24 by separating the control within the DEC function unit into a non-branching sequence controller preferably operating at the 26 BCLK,rate, and a branching sequence controller preferably operating at a fraction of the BCLK rate.
Memory sizes and access delay times are still further minimized by separating the control memory of branching controllers contained within the FA and DEC
function units into an address segment and an instruction segment.
A demultiplexer architecture according to the invention comprises an FA
function unit including Frame Alignment Logic (FAL) hardware controlled by a Programmable Frame Alignment Controller (PFAC), and accompanied by a DEC
function unit including Output Logic Hardware (OLH) controlled by a Programmable Decommutator Sequencer (PDS) controlled in turn by a Programmable Decommutator Sequencer Controller (PDSC).
According to another aspect of the present invention there is provided an apparatus for demultiplexing a PCM/TDM input data signal containing frame alignment signals that are used to achieve frame synchronization, said apparatus comprising:
frame alignment logic means for receiving said PCM/TDM input data signal, a bit clock signal having a predetermined bit clock rate derived from said input data signal, and a current instruction signal, for detecting said frame alignment signals, for generating a frame synchronization signal in response to the detection of a boundary of a frame in said input data signal, and for generating a frame alignment status signal;
a programmable frame alignment controller for receiving said bit clock signal and said frame alignment status signal, for generating said current instruction signal, and for controlling said frame alignment logic means;
output logic means for receiving said bit clock signal, said input data signal, and sequences of control words for decommutating sequences of bit formats that repeat within said frame, and for generating an output tributary signal, a data valid signal indicating that an output tributary signal has been generated, and a dejustification status signal indicative of a dejustification state of the output logic means;
a programmable sequencer for receiving said bit clock signal, and a next sequence instruction signal, for generating said sequences of control words that decommutate the sequences of bit formats that repeat within said frame, and for generating an instruction done signal; and a programmable sequences controller for receiving said frame synchronization signal, said dejustification status signal, and said instruction done signal, and for generating said next sequence instruction signal to cause said programmable sequences to generate said sequences of control words;
and wherein said output logic means and said programmable sequences are caused to operate at the bit clock rate of said bit clock signal, and wherein said programmable sequences controller is caused to operate at a fraction of said bit clock rate.
According to yet another aspect of the present invention there is provided an apparatus for demultiplexing a PCM/TDM input data signal containing frame alignment signals that are used to achieve frame synchronization, said apparatus comprising:
frame alignment means for detecting said frame alignment signals in said input data signal to locate the beginning of a frame, comprising:
frame alignment logic means (FAL) for receiving said PCM/TDM input data signal, a bit clock signal (BCLK) having a predetermined bit clock rate derived from said input data signal, and a current instruction signal (CI), for detecting said frame alignment signals, for generating a frame synchronization signal (P) in response to the detection of a boundary of a frame in said input data signal, and for generating a frame alignment status signal (FCSL); and programmable frame alignment controller means (PFAC) for receiving said bit clock signal (BCLK) and said frame alignment status signal (FCSL), for generating said current instruction signal (CI) for controlling said frame alignment logic means;
and dejustification and decommutation means (DEC) for decommutating sequences of bit formats that repeat within said frame, comprising:
output logic means (OLH) for receiving said bit clock signal (BCLK), said input data signal, and sequences of control words (CW) for controlling said output logic means to decommutate sequences of bit formats that repeat within said -7a-frame, and for generating at least one output tributary signal, a data valid signal indicating that an output tributary signal has been generated, and a dejustification status signal (DCSL) indicative of a dejustification state of the output logic means;
a programmable sequencer means (PDS) for receiving said bit clock signal (BCLK) and a next sequence instruction signal (NSI) for generating said sequences of control words (CW) that control said output logic means (OLH) in response to the next sequence instruction signal to decommutate said sequences of bit formats that repeat within said frame, and for generating an instruction done signal (IDONE); and a programmable sequencer controller means (PDSC) for receiving said frame synchronization signal (P), said dejustification status signal (DCSL) and said instruction done signal (IDONE), for generating said next sequence instruction signal (NSI) to control said programmable sequencer means (PDS);
and wherein said output logic means (OLH) and said programmable sequencer means (PDS) are caused to operate at the bit clock rate of said bit clock signal, and wherein said programmable sequencer controller means (PDSC) is caused to operate at a fraction of said bit clock rate.
Unlike Hubbard, the present invention does not require a frame buffer memory. The invention has the advantage that there is no requirement to store a whole frame of bit-signals. Data bits are decommutated one by one as the TDM
stream proceeds through the decommutation function. In contrast to Huffman, the invention provides for state controller implementation efficiency and particularly programmability.
IN THE DRAWING
Embodiments of the present invention will now be described more fully with reference to the accompanying drawings in which:
Fig. 1 represents a simplified PCM/TDM communications link;
Fig. 2 is an example PCM/TDM format with contiguous F bits;
-7b-mso~~~
1 Fig. 3 is an example PCM/TDM format with distributed F

2 bits, just ification control JC bits, and justification J bits:

3 Fig. 4 represents the basic architecture for preferred 4 embodiments of PCM/TDM
demultiplexers according to the present invention:

6 Fig. 5 shows the FA function implemented by FAL and PFAC:

7 Fig. 6 illustrates a generic PDSC architecture;

8 Fig. 6a shows a PDSC in a first embodiment:

9 Fig. 6b shows a PDSC in a second embodiment;

Fig. 6c- shows a PDSC in a third embodiment;

11 Fig. 6d shows a PDSC in a fourth embodiment:

12 Fig. 7 shows a PDS embodied in preferred Sequence Program 13 Memory (SPM) and Sequence Control Logic (SCL) components;

14 Fig. 8 shows OLH hardwired in DeJustification Logic (DJL) and DeCommutation Logic (DCL) circuits;
and 16 Fig. 9 connects the FA function of Fig. 5 and the DEC

17 function of Figs.
6-7, 8 in an example implementation.

The present invention provides an architecture for a 21 PCM/TDM demultiplexer as shown in Fig. 4 including individual 22 coordinated FA and DEC functions. The invention minimizes its 23 reliance on reprogrammable memory cycling at the BCLK rate, 24 which at the present state of technology may rise to as high as 50 MHz. A balance of hard-wired with programmable logic 26 preserves demultiplexing speed and programming flexibility.

2160~~3~
1 Frame Alignment Circuit Description 2 The candidate FA pattern word assembly and matching step 3 of the FA function must keep pace with BCLK, and is therefore 4 implemented by hardwired logic unit FAL. Referring to Fig. 5, the FAL is controlled by the PFAC, which is programmed with 6 short sequences of microcode which it executes at the rate of 7 one microinstruction per cycle of BCLK. The PFAC preferably 8 comprises a branching programmable state machine having 9 control storage partitioned into FAL State address MEMory (FSMEM) and FAL Instruction MEMory (FIMEM) segments, and 11 having Next Instruction (NI) output dependent only upon a 12 current state stored in a State REGister (SREG). The memory 13 segments are each small enough to be accessed at a suitable 14 design margin faster than the fastest specified BCLK rate.
The FSMEM presents PF_AC Next-State Address (FNSA) signals to 16 SREG. Successive FNSAs are latched on successive cycles of 17 BCLK and presented as P_FAC Current State Address (FCSA) 18 signals to address lines of FSMEM and FIMEM. Consequently, 19 FIMEM produces the NI signal. The next cycle of BCLK advances signal NI through Instruction REGister (IREG) to emerge as a 21 Current Instruction signal (CI). CI is applied to PFAC Status 22 MUltipleXer (FSMUX) to select an input FAL Condition Status 23 Line (FCSL) which is used as a Selected Status Bit (SSB) 24 preferably to one address line of FSMEM, to facilitate branching of programs in the controller PFAC. An example 26 FSMEM can store 64 states of which each can branch two ways, r._ 1 which provides up to 128 addresses. CI is received in FAL
2 through FAL instruction DECoder (FDEC). FAL also includes 3 serial/parallel FAL Shift Register (FSR), Interleave Pattern 4 RAM (IPR), initializable ADDress CounTer (ADDCT), reference FA
Pattern Register (FPR), _FAL Mask Register (FMR), FAL Masked-6 Bit Comparator (FMBC), FAL DeteCT if all comparisons are TRUE
7 circuit (FDCT), _FAL Flip-Flop (FFF), and a bank of (preferably 8 8) PRogrammable CounTeRs (PRCTRs). In this example, PFAC
9 control memory data is organized as follows:
FAC memor y bit assignment:

Bits Value Meaning FSMEM Secr ment (0:5) 0 to 63= FNSA

FIMEM Se_ ent (0:1) 0= received data bit to be shifted serially into the designated FSR;

1= write contents FSR into IPR;
of 2= increment ADDCT 4:
+

3= IPR read parallel to designated FSR;

(2:4) 0 to 7= designated PRCTR;

(5:6) 0= global PRCTR rese t;

1= increment designa ted PRCTR;

2= reset designated PRCTR;

3= increment ADDCT 1;
+

(7:10) 0 to 15= FCSL selection FSMUX.
by 23 Speed goals for sync-lock onto FA signals dispersed 24 through frames of particular durations are related to IPR
25 sizes. An FAL embodied in an IC preferably economizes memory 26 area by tolerating slower FA-searches. An IPR capable of _ 216Q~~1 1 storing 1/4 of all the potential candidate FA-pattern bits 2 implies that for it to attain FA-sync will sometimes require 3 as long as four frame intervals. To achieve FA-sync, the IPR
4 executes repetitions of:
1. Shifting a 4th-received PCM/TDM bit into the FSR for 6 assembly with candidate FA pattern bits loaded in 7 step 4, thus producing an updated set of candidate 8 FA pattern bits;
9 2. Writing the updated candidate FA pattern bits back into its respective location in the IPR;
11 3. Incrementing ADDCT by 4; and 12 4. Parallel-loading the IPR's newly addressed contents 13 into the FSR in preparation for step 1.
14 FDCT senses outputs from FMBC. Only when there is a match between IPR and FPR in the bit positions indicated by 16 FMR, FDCT produces a logic TRUE signal. The program in PFAC
17 typically uses counters in PRCTR to keep track of its progress 18 in analyzing the signal stream. It can increment them, reset 19 them, and test them to detect when they are at their terminal count. If the program in PFAC senses that a set of 4th-21 addressed bit patterns has been collected without finding a 22 match, it preferably operates to incremented ADDCT by 1 and 23 repeat the search on the next set of 4th-addresses until a 24 match is found.
The Fig. 5 FAL can test distributed bits for FA-words 26 beginning in any of 64 time-slots during each frame.

1 To inspect only one time-slot for a starting bit in each 2 frame, an alternate embodiment of FAL can omit the IPR and 3 ADDCT. Also, contiguous-bit FA pattern-searches which shift 4 bits into the FSR at the BCLK rate do not need the IPR.
6 Frame Alignment Process Description 7 PCM/TDM signals are received through circuits which 8 recover MCLK (Fig. 1) timing as BCLK, which accompanies 9 PCM/TDM stream bits arriving at the demultiplexer of Fig. 4.
Received PCM/TDM signal streams expected to have non-11 contiguous FA-bits are searched for possible starting bits at 12 multiple positions. Each time the assembly of a bit completes 13 a candidate FA-pattern, the assembled pattern-word is masked 14 by FMR and compared in FMBC against a reference FA pattern stored in FPR. Ordinarily, upon the first match, to tag an 16 identified frame boundary, FAL issues a frame-synch Pulse (P).
17 FA-synch losses are not ordinarily conceded until after 18 several failed comparisons. Preferably, FA-loss thresholds 19 are programmable through monitoring by the program in the PFAC
of the comparison outcomes in counters such as PRCTR (Fig. 5).
21 Achieving FA in some TDM formats next involves searching 22 with a multi-frame pattern for a MF boundary. MF boundaries 23 have pre-determined relationships to single-frame boundaries.
24 Hence, MFA word searches need only compare a limited number of positions for potential MFA word start bits, and do not need 26 the IPR.

1 Deiustification and Decommutation 2 In decommutating a received PCM/TDM signal stream, 3 various short, structured sequences of bits are manipulated 4 repetitively in a manner predetermined by the particular PCM/TDM multiplexing format, in order to distribute data bits 6 to their respective output tributaries. Dejustification is a 7 modification of the decommutation action. Justification 8 control bits contained in the signal stream are detected, and 9 depending on their interpretation in the particular multiplexing format, a bit from the signal stream may be sent 11 to an output tributary, modified and then sent, or deleted.
12 The prior art MPX-100 used one state-machine to directly 13 control both its dejustification and its decommutation OLH.
14 Current-state status or condition inputs could cause the state machine used in the MPX-100 to alter its output immediately.
16 However, analysis of MPX-100 operations has ascertained that 17 decommutation processes can be successfully performed by a 18 state machine whose outputs depend only upon preceding-states 19 and conditions. This is the response exhibited by the type of branching state machines used in the present invention. Such 21 machines cycle faster than equivalent machines of the type 22 used in the MPX-100.
23 TDM decommutation and dejustification control functions 24 according to the present invention are implemented in a combination of two machines. One is a branching state machine 26 operating preferably at a lower clock rate than BCLK, 1 controlling a second, preferably smaller, simpler non-2 branching state machine operating at the BCLK rate.
3 Fig. 4 shows the decommutation and dejustification 4 function according to the present invention consisting of an OLH, a PDS and a PDSC. The OLH typically receives short 6 sequences of Control Word (CW) signals from the PDS as a 7 result of the PDS receiving a particular Next Sequence 8 Instruction (NSI) from the PDSC. Each short sequence of CW
9 signals typically controls the OLH to decommutate sequences of bit formats which repeat within a frame. The PDS outputs CWs 11 at the BCLK rate. The PDS is preferably a non-branching 12 sequences controlled by a counter so that it begins executing 13 the CW addressed by the NSI and then cyclically executes 14 successive CWs until a CW is reached which has the Sequence Done (SDONE) bit turned on, at which time the sequences 16 decrements the Sequence Repeat Number (SRN) from the NSI, and 17 either signals Instruction Done (IDONE) if the SRN reached the 18 limit count, or starts executing CWs beginning once again with 19 the CW addressed by the NSI. The IDONE signal causes the PDSC
state machine to cycle and issue a new NSI signal to the PDS
21 and the process repeats. The sequence generation control 22 process of the PDSC can be made conditional by testing the FA
23 synch-lock line P, or OLH condition status lines DCSL. Typical 24 condition status signals are the status of justification control actions and terminals counts of counters.

1 The single branching state machine in the prior art MPX-2 100 had a single segment control memory which cycled at, and 3 limited, the BCLK rate. It was also large compared to the 4 present invention because each location contained storage for a state, an instruction, and an alternate state and 6 instruction.
7 In contrast, the present invention has only a relatively 8 small memory SPM operating at BCLK speed. The larger DMEM
9 operates preferably at one-fourth BCLK speed, and is smaller than prior art MPX-100 memory due to the different structure 11 of the branching controller PDSC. The PDSC is the type of 12 controller whose output depends only on the current state and 13 not on the current input, so it need not store alternate 14 instruction and state in each location as did the memory of the MPX-100 controller. These improvements together allow PDS
16 and PDSC memory to occupy 30% less total space than MPX-100 17 memory, while providing comparable performance.
lg Conditional PDSC instructions are supported for branching 19 to another part of the program or calling a subroutine in the usual manner in computing controllers. When an NSI is a 21 procedure CALL, SUBroutine Control (SUBC) bits cause Next 22 State Logic (NSL) Subroutine-Return Register (SRR) (detailed 23 in Fig. 6d) to increment the value of, and then save, the 24 normal Decommutator Next-State Address (DNSA). When the body of the subroutine has been completed, a RETURN instruction 26 generates SUBC field bits to designate the SRR as the source 216050th __ ~.
1 for the Decommutator Current-State Address (DCSA) word.
2 The "IF... THEN GOTO" instruction can be looped and 3 further nested by incrementing and testing OLH registers which 4 are similar to PRCTR in Fig. 5. Referring to Fig. 6a, for conditional instructions the branch condition select (IF) bits 6 direct Status MUltipleXer (DSMUX) to select an OLH Condition 7 Status Line (DCSL) or line P to test and thereby influence the 8 PDSC output on the next cycle.
9 The Fig. 6 generic PDSC is shown in alternate embodiments in Figs. 6a, 6b, 6c and 6d, each of which partitions DMEM
11 differently. PDSCs in the embodiments of Figs. 6a and 6b have 12 DMEMs partitioned into Decommutator State MEMory (DSMEM) 13 segments a and b, respectively (DSMEMa, DSMEMb) and 14 Decommutator Instruction MEMory (DIMEM) segments a and b, respectively (DIMEMa, DIMEMb). In Fig. 6a, a DNSA is output 16 from DSMEM when addressed jointly by DCSA bits and by a DCSL
17 bit selected by the IF signal. The Fig. 6a DSMEMa of 256 18 words X 7 bits is exchangeable for the Fig. 6b DSMEMb of 128 19 words X 14 bits. Fig. 6b DSMEMb outputs two parallel 7-bit fields, providing both a Next-State Address Word (NSAW) and a 21 Next-State Branch Address Word (NSBAW), to a Next-State 22 Multiplexer (NSMUX) which selects either NSAW or NSBAW as the 23 DNSA.
24 Fig. 6c shows the PDSC in a third embodiment having its state address and instruction memory collected in Decommutator 26 Instruction and State MEMory unit c (DISMEMc), which remains 216Q~fl4 1 equivalent in total capacity to DSMEMb plus DIMEMb of Fig. 6b.
2 All three of these DMEM embodiments a,b,and c (DMEMa, DMEMb, 3 and DMEMc) have equivalent storage capacities of 3456 bits.
4 FIg. 6d shows a further improvement in memory requirements over the Fig. 6a, 6b and 6c embodiments.
6 Decommutator Instruction and State MEMory unit d (DISMEMd) 7 area and, therefore, access time is reduced almost by half in 8 the embodiment-shown in Fig. 6d. This embodiment takes 9 advantage of PDSC programs being structurable mostly "in-line," branching only infrequently.
11 In the Fig. 6d embodiment, next-state addresses are 12 generated simply by incrementing the DCSA. With each IDONE
13 signal Decommutator Sequencer State Register (DSSR) stores the 14 incremented DCSA, which is then selected as the DCSA.
CALL and GOTO instructions are executed in two access 16 cycles of DISMEMd. Conditional instructions are executed by 17 selecting an input for DSMUX to select either the Decommutator 18 Branch State Register (DBSR) or the DSSR as the source for 19 DCSA. By placing the Branch State Address (BSA) in the DISMEMd address just after the CALL or GOTO instruction, the 21 second DISMEMd access outputs the BSA in place of NSI and BSA
22 as input into the DBSR. The DBSR output is consequently 23 selected as the new DCSA.
24 Subsequent DCSA's are generated by incrementing DCSA and storing it in DSSR. A RETURN is executed in all Fig. 6 26 embodiments by storing return a address in the SRR.

1 Decommutator Dimensions 2 The PDSC is preferably embodied as illustrated in Fig.
3 6d. The majority of standard or non-standard format PCM/TDM
4 decommutation programs are executable using Decommutator~
Instruction MEMory (DIMEM) of 128 words including fields of 6 SUBroutine Control (SUBC) in bits 11-12, branching control 7 (IF) in bits 8-10, and Next Sequence Instruction (NSI) for the 8 PDS in bits 0-7. NSI is further divided into Sequence 9 Repetition Number (SRN) in bits 4-7, and Current Scan Sequence (CSS) in bits 0-3.
DIMEM fields:
Bits Value Meaninct (0:3) 0 to 15 MSBs of starting address for next scan-sequence in the PDS;

(4:7) 0 to 15 Number of repetitions to execute next scan-sequence;

(8:10) 0 to 7 Selected DCSL condition status lines;

(11:12) 0= NORMAL (the DCSA source is DSR);

increment DCSA after each DISMEMd access, and store incremented DCSA

in DSR.

1= CALL subroutine (while the current NSI is being executed, increment DCSA to again access DISMEMd. The NSI field is used not as a next instruction but as a branch address and stored in DBSR for the next DCSA. DCSA is incremented and stored as the return address in SRR.

2= RETURN from subroutine (select SRR contents as DNSA).

3= GOTO same as CALL, except without return address in SRR.

2I605~4 1 The PDS executes "scan-sequences" of micro-instructions 2 to manipulate input PCM/TDM signal bits. A specific scan-3 sequence and its number of repetitions are designated by the 1 NSI. While the PDS is executing this previously loaded NSI, 2 the PDSC sets up the next NSI. When a scan-sequence's last 3 cycle has been completed the PDS asserts an IDONE signal which 4 loads the waiting NSI into the PDS, and cycles the PDSC to select the following NSI.
6 Thus the PDSC cycles through its states at the IDONE
7 rate, or at twice the IDONE rate for CALL or GOTO
8 instructions. The maXimum PDSC design cycle rate can be 9 adjusted by limiting the length of the shortest (fastest) scan-sequence which the PDS will execute. A practical limit 11 allows the PDSC to cycle no faster than one-fourth the rate of 12 the PDS, which cycles at the BCLK rate.
13 The PDS is shown in Fig. 7 embodied in sequence program 14 memory (SPM), and in sequence control logic (SCL) in turn including a Sequence Control Register (SCR), a Sequence Cycle 16 Counter (SCC), Terminal Logic (TL) and a Sequence Program 17 Counter (SPC). The SPM has a capacity of preferably 256 words 18 of 8 bits each writable with data fields defining micro-19 instructions such as:

2160~0~.
SPM Fields:

Bits Value Meaninct (0:2) 0 to 7 Tributary number (3:6) 0= data slot: output data bit 1= data slot: output inverted data bit 2= data slot: output assembled word 3= output logic "0"

4= output logic "1"

5= control slot: tributary control bit 6= control slot: common control bit 7= control slot: enable a comparison (in Fig. 8) 8= positive justification slot 9= negative justification slot (7) 1= SDONE

13 SPM output CW micro-instructions are used as steps in 14 preferably (4 to 16) clock cycles of (any of 16) scan-15 sequences executed in response to NSIs.
16 Assuming the PDS has already returned an IDONE signal, 17 the NSI waiting to be input to the SCL (as shown in~Fig. 7) is 18 latched by the SCR and (then) output in parallel as a 4-MSB
19 Current Scan Sequence (CSS) field indicating a starting 20 address, and a four-LSB field indicating a SRN of times to 21 repeat addressing, of a scan sequence in the SPM. The LSBs 22 initialize and BCLK increments LSBs through SPM addresses to 23 output CW bits (0:6) to the OLH.
24 ~ SPM scan-sequences terminate when a CW contains a 'one' 25 in bit No. 7 (SDONE) which increments SCC, resets the SPC and 26 restarts execution of the current scan-sequence.

2160~~4 1 The PDSC sets up a following NSI while current scan-t sequence instructions are re-executed until their final 3 repetition has been completed by the PDS.
4 When the SCC reaches its terminal count =SRN, the TL
allows SDONE to generate an IDONE signal which strobes the SCR
6 to latch in another NSI. Referring again to Figs. 6, the 7 IDONE signal simultaneously strobes the NSL to latch another 8 DNSA for feedback as a new DCSA. Additional NSIs may be used 9 to extend to 32 or beyond the number of repetitions of given sequence.
11 An example scan-sequence consists of eight CWs for 12 causing the OLH to decommutate data signals to eight 13 tributaries in a selected order. CW signals are equivalent to 14 strings of in-line code repetitively "calling" the "hardware subroutine" Fig. 8 OLH to perform dejustification or 16 decommutation operations.

18 Data Outuut Loctic Hardware 19 The architecture according to the present invention for controller-sequences-hardware for decommutation is well 21 adapted also for dejustifying signals in synchronous and/or 22 plesiochronous multiplexing environments.
23 Preferably, conditional data signal bit manipulations 24 such as dejustifications are performed in hardwired logic by the OLIi rather than by having the PDSC selecting a 26 justification control program sequence for this purpose to be 1 exercised by the PDS.
2 The OLH includes dejustification control logic (DJL) and 3 decommutation control logic (DCL). The Output Interface Logic 4 (OIL), besides a data signal, also provides a "data valid/ready" signal, controlled by the Decommutator data field 6 DECoder DDEC.
7 Fig. 8 represents DJL hardware for assembling and 8 interpreting Justification Control words from JC bits as noted 9 for the example in Fig. 3. DJL includes a Justification data field DECoder and data select (JDEC), Shift Logic (SL), 11 Dejustification Shift Registers (DSR), Dejustification Pattern 12 Registers (DPR), Dejustification Mask Registers (DMR), 13 Dejustification Masked-Bit Comparators (DMBC), a 14 Dejustification DeteCT if all bits compare register (DDCT) and Flip-Flops (DFFs).
16 Received PCM/TDM stream bits which are candidates for 17 being bits JC are shifted singly into one of the 8 DSR
18 selected by tributary select bits (0:2) of CW. Bits JC may be 19 contiguous in a frame or distributed within a frame or across multiple frames. The DJL can assemble bits from arbitrary 21 formats because bit JC shifting is controlled by the CW input 22 to JDEC. The Dejustifier Shift Registers' (DSR) contents are 23 compared by Dejustifier Masked Bit Comparator (DMBC) against a 24 mask and a reference pattern retrieved from respective registers Dejustifier Mask Register (DMR) and Dejustifier 26 Patter Register (DPR). The Dejustifier DeteCT-if-all-bits-2160~0~
1 compare circuit (DDCT) asserts a TRUE signal if all non-masked 2 comparing bits match. Once a Justification Control word has 3 been assembled in a DSR, a JDEC enable-comparison (RESET) 4 signal latches the DDCT output into one of the eight DFF's.
Preferably, an initialization procedure configures DJL
6 with rules for specific justifications. For example, common 7 JC words are strings of an odd number of "1"s for which the 8 rule is to recognize that the majority of bits in the JC are 9 "1"s. In this example, the initialization procedure configures either SL to shift only "1"s. Then, DMBC tests for 11 strings of (n/2)+1 "1"s, where "n" is the number of "1"s in 12 the JC word. Thus, for JC words of five "1"s (11111), DMBC
13 tests for strings of a majority out of five, i.e., at least 14 three "1"s, e.g., lllxxx.
Fig. 8 shows the DCL, which includes a DDEC, a Data 16 Selector (DS), a set of 16 FFs, and oIL. .CW ordinarily has 17 its bits (3:6) set to equal zero and causing DS to select the 18 current PCM/TDM data bit signal as the data source. However, 19 as a result of dejustification, CW bits (3:6) may either =1 causing DS to select the PCM/TDM data bit complement, =4 to 21 select a logic one, or =3 to select a logic zero. The DS
22 output data bit and the DDEC data Valid/Ready bit set 23 whichever pair of FFs is designated by tributary select bits 24 (0:2) of CW.
Returning to Fig. 8, the justification control signal 26 test outcomes are output as DCSL signals to the PDSC. At the 1 estimated time for executing a justification action, the PDSC
2 produces an NSI conditioned on a DCSL status. The NSI then 3 controls the PDS to output a CW which causes the DCL (Fig. 5) 4 to control the data valid/ready bit and thereby perform a justification action as described above. If there is a data 6 bit contained in the current time slot then the data 7 valid/ready signal will be asserted to indicate that a 8 tributary data is being output. Conversely, if there is not a 9 data bit in the current time slot, then the data valid signal will not be.asserted.
11 In Fig. 8 the OIL outputs bit-serial data and data-valid 12 from up to eight tributaries. Other embodiments of OIL could 13 output word-serial or word-parallel data signals from each 14 possible tributary. OIL contains sufficient registers and logic for an application to prepare output word-parallel data 16 from multiple tributaries, and ready signals for each 17 tributary.

19 Initialization The present invention advantageously facilitates 21 INITialization by a separate function (INIT), which Fig. 4 22 shows as an off-line configuration control from which, 23 preferably, upon power up and/oi reconfiguration, 24 configuration and initialization information is input through a serial port and transmitted to the various elements of the 26 demultiplexer by way of conventional additional data paths not 2160 ~~~
1 shown in drawings 4 through 9. Initialization signals are 2 down-loaded first, to load micro-programs into both 3 controllers' state and instruction memories; second, to load 4 the scan-sequencer micro-program into the SPM; third, to configure the FAL, DJL and DCL output logic hardware; fourth, 6 to load terminal-count values into counters in OLH; and 7 finally, to load OLH correlation patterns into pattern 8 registers and masks into mask registers. The MPX-100 9 performed initialization functions within the state machine, although the MPX-100 still required off-line down-loading of 11 its state memory control store. The present invention's 12 combination of down-loading memories and configuring hardware 13 significantly reduces the control store size requirements, at 14 the modest expense of additional hardware which is a good tradeoff to minimize control store sizes.
16 It will be obvious to one skilled in the art that this 17 invention relates to a system for optimizing the speed and 18 flexibility of a PCM/TDM demultiplexer where constraints must 19 be observed as to the total volume of logic circuitry that may be used, and that, as the technology for packaging logic 21 inevitably improves, the principles described herein may be 22 applied to produce embodiments of this invention that are 23 faster, more compact, or both. In addition, it is clear that 24 other functional elements not described herein may be included within the structure of the preferred embodiment, such as a 26 feedthrough descrambler.

2160~~
--- ~.;
What is claimed is:

Claims (11)

1. We Claim:
   
   Apparatus for demultiplexing a PCM/TDM input data signal containing frame alignment signals that are used to achieve frame synchronization, said apparatus comprising:
   frame alignment logic means for receiving said PCM/TDM input data signal, a bit clock signal having a predetermined bit clock rate derived from said input data signal, and a current instruction signal, for detecting said frame alignment signals, for generating a frame synchronization signal in response to the detection of a boundary of a frame in said input data signal, and for generating a frame alignment status signal;
   a programmable frame alignment controller for receiving said bit clock signal and said frame alignment status signal, for generating said current instruction signal, and for controlling said frame alignment logic means;
   output logic means for receiving said bit clock signal, said input data signal, and sequences of control words for decommutating sequences of bit formats that repeat within said frame, and for generating an output tributary signal, a data valid signal indicating that an output tributary signal has been generated, and a dejustification status signal indicative of a dejustification state of the output logic means;
   a programmable sequencer for receiving said bit clock signal, and a next sequence instruction signal, for generating said sequences of control words that decommutate the sequences of bit formats that repeat within said frame, and for generating an instruction done signal; and a programmable sequencer controller for receiving said frame synchronization signal, said dejustification status signal, and said instruction done signal, and for generating said next sequence instruction signal to cause said programmable sequencer to generate said sequences of control words;
   and wherein said output logic means and said programmable sequencer are caused to operate at the bit clock rate of said bit clock signal, and wherein said programmable sequencer controller is caused to operate at a fraction of said bit clock rate.
2. 2. The apparatus of claim 1 wherein said programmable frame alignment controller comprises a control memory operative at said bit clock rate that includes a state segment memory for storing next state address signals corresponding to a memory location of a next instruction signal, and an instruction segment memory for storing said next instruction signal.
3. 3. Apparatus for demultiplexing a PCM/TDM input data signal containing frame alignment signals that are used to achieve frame synchronization, said apparatus comprising:
   frame alignment means for detecting said frame alignment signals in said input data signal to locate the beginning of a frame, comprising:
   frame alignment logic means (FAL) for receiving said PCM/TDM
   input data signal, a bit clock signal (BCLK) having a predetermined bit clock rate derived from said input data signal, and a current instruction signal (CI), for detecting said frame alignment signals, for generating a frame synchronization signal (P) in response to the detection of a boundary of a frame in said input data signal, and for generating a frame alignment status signal (FCSL); and programmable frame alignment controller means (PFAC) for receiving said bit clock signal (BCLK) and said frame alignment status signal (FCSL), for generating said current instruction signal (CI) for controlling said frame alignment logic means; and dejustification and decommutation means (DEC) for decommutating sequences of bit formats that repeat within said frame, comprising:
   output logic means (OLH) for receiving said bit clock signal (BCLK), said input data signal, and sequences of control words (CW) for controlling said output logic means to decommutate sequences of bit formats that repeat within said frame, and for generating at least one output tributary signal, a data valid signal indicating that an output tributary signal has been generated, and a dejustification status signal (DCSL) indicative of a dejustification state of the output logic means;
   a programmable sequencer means (PDS) for receiving said bit clock signal (BCLK) and a next sequence instruction signal (NSI) for generating said sequences of control words (CVO that control said output logic means (OLH) in response to the next sequence instruction signal to decommutate said sequences of bit formats that repeat within said frame, and for generating an instruction done signal (IDONE); and a programmable sequencer controller means (PDSC) for receiving said frame synchronization signal (P), said dejustification status signal (DCSL) and said instruction done signal (IDONE), for generating said next sequence instruction signal (NSI) to control said programmable sequencer means (PDS);
   and wherein said output logic means (OLH) and said programmable sequencer means (PDS) are caused to operate at the bit clock rate of said bit clock signal, and wherein said programmable sequencer controller means (PDSC) is caused to operate at a fraction of said bit clock rate.
4. 4. Apparatus for demultiplexing as defined in claim 3 wherein said programmable frame alignment controller means (PFAC) includes control memory means (FSMEM, FIMEM) operative at said bit clock (BCLK) rate for storing next state address signals (FNSA) corresponding to a memory location of a next instruction signal (NI) and for storing said next instruction signal, (NI), respectively, and which is comprised of a state segment memory means (FSMEM) for storing said next state address signals (FNSA), and an instruction segment memory means (FIMEM) for storing said next instruction signal (NI).
5. 5. Apparatus for demultiplexing as defined in claim 4 wherein said frame alignment logic means (FAL) includes:
   instruction decoder means (FDEC) for receiving said current instruction signal (CI) from said programmable frame alignment controller means (PFAC), for decoding said current instruction signal (CI), for generating a plurality of control signals;
   address counter means (ADDCT) for receiving control signals from said instruction decoder means (FDEC), for receiving said bit clock signal (BCLK), and for generating interleave pattern memory address signals in response thereto;
   
   shift register means (FSR) for receiving control signals from said instruction decoder means (FDEC), for receiving a partially assembled candidate frame alignment pattern word from an interleave pattern memory means (IPR), for receiving said PCM/TDM input data signals, for combining said partially assembled candidate frame alignment pattern word and said PCM/TDM input data signals to generate an updated candidate frame alignment pattern word, and for sending said updated candidate frame alignment pattern word to said interleave pattern memory means (IPR), and wherein a first control signal from said instruction decoder means (FDEC) controls said shift register means (FSR) to receive and store output signals from said interleave pattern memory means (IPR) in parallel format, and wherein a second control signal from said instruction decoder means (FDEC) controls said shift register means (FSR) to serially shift the contents of the shift register means (FSR) and said PCM/TDM input data signals;
   said interleave pattern memory (IPR) comprising address means for receiving said interleave pattern memory address signals from said address counter means (ADDCT), control means for receiving control signals from said instruction decoder means (FDEC), a memory means for temporarily storing a plurality of candidate frame alignment pattern words, data input means for receiving said updated candidate frame alignment pattern word from said shift register means (FSR), data output means for sending said partially assembled candidate frame alignment pattern word to said shift register means (FSR) and for sending an assembled candidate frame alignment pattern word to masked bit comparison means (FMBC);
   pattern register means (FPR) for storing and outputting a predetermined frame alignment pattern word;
   mask register means (FMR) for storing and outputting a predetermined frame alignment pattern comparison mask word;
   said masked bit comparison means (FMBC) comprising means for receiving said predetermined frame alignment pattern word, said predetermined frame alignment pattern comparison mask word, and said assembled candidate frame alignment pattern word from said interleave program memory (IPR), and for generating bit comparison result signals according to a match or no match between bits in said predetermined frame alignment pattern comparison word and bits in said assembled candidate frame alignment pattern word, and wherein said bits are defined by said predetermined frame alignment pattern comparison mask;
   detection means (FDCT) for receiving said bit comparison result signals, and for producing an equality signal responsive to a result of true in all of said bit comparison result signals;
   a flip-flop means (FFF) for storing said equality signal produced by said detection means (FDCT) and for producing said frame synchronization signal (P) that indicates a detection of a boundary of said frame, said flip-flop means receiving a control signal from said instruction decoder means; and a programmable counter means (PRCTR) for receiving control signals from said instruction decoder means (FDEC), and for producing said frame alignment status signal (FCSL) for use by said programmable frame alignment controller means (PFAC).
6. 6. Apparatus for demultiplexing as defined in claim 3 wherein said instruction done signal (DONE) is generated at a rate lower than the rate of said bit clock signal and is used as a clock for said programmable sequencer controller means (PDSC), and wherein said programmable sequencer controller means (PDSC) comprises:
   next state logic means (NSL) for receiving a next state address signal (DNSA) corresponding to a memory location of a next sequence instruction signal (NSI) that is executed, a subroutine control signal (SUBC) and said instruction done signal (IDONE), for incrementing the value of the next state address signal (DNSA) to produce a current state address signal (DCSA) in response thereto that corresponds to the memory location of a next sequence instruction signal (NSI) that is to be executed; and a memory means (DMEM) for receiving said current state address signal (DCSA), said instruction done signal (IDONE), said dejustification status signal (DCSL) and said frame synchronization signal (P), and for generating said subroutine control signal (SUBC), said next state address signal (DNSA) and said next sequence instruction signal (NSI), wherein said next sequence instruction signal (NSI) is adapted to control said programmable sequencer means (PDS) and change when said current state address signal (DCSA) changes.
7. 7. Apparatus for demultiplexing as defined in claim 6 wherein said memory means (DMEM) of said programmable sequencer controller means (PDSC) comprises:
   instruction memory means (DIMEMa, DIMEMb) for receiving said current state address signal (DCSA), and for storing and outputting data including said next sequence instruction signal (NSI); and a next state address memory means (DSMEMa, DSMEMb) for receiving said current state address signal (DCSA), said dejustification status signal (DCSL), and said frame synchronization signal (P), and for storing and outputting data comprising said next state address signal (DNSA).
8. 8. Apparatus for demultiplexing as defined in claim 6 wherein said memory means (DMEM) includes an instruction and address memory means (DISMEMc) for receiving said current state address signal (DCSA), and for storing and simultaneously outputting said next state address signal (DNSA) and said next sequence instruction signal (NSI).
9. 9. Apparatus for demultiplexing as defined in claim 6 wherein said memory means (DMEM) includes:
   next instruction and next branch address memory means (DISMEMd) for receiving said current state address signal (DCSA), and for storing and alternately outputting said next sequence instruction signal (NSI) and a next state branch address signal (NBSA) comprising said next sequence instruction signal (NSI) that is used as a branch address; and logic means (DBSR, NSMUX, DSMUX) for receiving said next state branch address signal (NBSA), said dejustification status signal (DCSL) and said frame synchronization signal (P), and generating said next state address signal (DNSA) from said next state branch address signal (NBSA) or from a result of performing an arithmetic operation (.SIGMA.+1) on a previously generated next state address signal (DCSA).
10. 10. Apparatus for demultiplexing as defined in claim 6 wherein said programmable sequencer means (PDS) includes:
    sequence control logic means (SCL) for receiving said next sequence instruction signal (NSI), said bit clock signal (BCLK) and a last step signal (SDONE), and for generating a current scan sequence signal (CSS) and an output signal indicative of an address of a control word; and sequence program memory means (SPM) for storing control words (CW) therein, for receiving the current scan sequence signal (CSS) and said output signal indicative of the address of a control word (CW) stored therein, for providing said last step signal (SDONE) when a final control word (CW) in a sequence of control words has been output, and for generating said sequences of control words (CW).
11. 11. Apparatus for demultiplexing as defined in claim 10 wherein said sequence control logic means (SCL) comprises:
    sequence control register means (SCR) for receiving said next sequence instruction signal (NSI), for providing said current scan sequence signal (CSS) to said sequence program memory means and for providing a sequence repeat signal (SRN);
    sequence cycle counter means (SCC) for storing said sequence repeat signal, for counting the number of times a sequence of control words has been scanned in response to said last step signal (SDONE), and for outputting a cycle complete signal when sequence of control words is scanned the number of times indicated by the sequence repeat signal;
    terminal logic means (TL) for receiving said bit clock signal (BCLK), said last step signal (SDONE), and said cycle complete signal, and for outputting said instruction done signal (IDONE) for loading said sequence control register (SCR) and indicating to said programmable sequencer controller means that said sequence of control words has ended; and sequence program counter (SPC) means resetable to a predetermined value in response to said last step signal (SDONE) and operative to increment in response to said bit clock signal (BCLK), for providing addresses of successive control words of said sequence of control words to said sequence program memory means.