Note: Descriptions are shown in the official language in which they were submitted.
D-24,7l7
~L23~6~1~
ASYNCHRONOUS SIGNALING FOR DIGITAL COMMUNICATION CHANNEL
BY
MICHAEL J. GREEN AND JAMES B. MC KAY
BACKGROUND OF THE INVENTION
This invention relates to method and apparatus for performing signal-
ing functions in a digital communication system and more particularly to
improved method and apparatus for per~orming asynchronous s;gnaling in a
digital communication channel.
The conventional method of communicating signaling information in a
synchronous communication link or channel is to multiplex bits of a
signaling word with channel information bits with due regard to the
framing format. With synchronous signaling techniques the equipment
defines when a s;gnaling word is allowed to start and thus an inherent
variable delay occurs between the time a random change to a d;fferent
signaling message is desired and the time when it is completely received.
Asynchronous signaling techniques, however, convey signaling messages at
times that are not predictable, i.e., the receiver has no knowledge as to
when a signaling word will start. Also since there is no transmission of
any signaling information until a different signaling message is to be
transmitted, failure of the asynchronous communication system can occur
without the system being aware of this failure.
An object of this invention is the provision of improved method and
apparatus for performing asynchronous signaling.
--1--
D-24,717
Another object is the provision of improved method and apparatus
which continuously transmits digital signaling words and makes decisions
as to the transmitted signaling word for each bit of signaling information
and which does not require information as to the start or stop of a parti-
cular signaling word.
SUMMARY OF INV~NTION
In accordance with this invention, an asynchronous signallng method
in a digital communication system including transmitting and receiving
equipment for multiplexing and demultiplexing digital traffic information
signals and digital signaling information signals comprises the steps of
defining a plurality of signaling states Sl-SM; selecting a plurality of
M unique N-bit primary digital code words Sml each defining a different
one of the signal states Sl-SM and each having N-l additional ordered
permutations of the order of the bits thereof, with the additional ordered
permutations being designated secondary code words; selecting a particular
state Ss for transmission; serially producing bits Bl-BN of one of the
primary and secondary code words for the selected signaling state Ss at a
slgnaling clock rate; multiplexing signaling bits with traffic information
bits at signaling time slots in a bit stream where the signaling time
20 slots occur at the signaling clock rate; transmitting the multiplexed bit
stream to receiver equipment; extracting a signaling clock signal from
the multiplexed bit stream in the receiver equipment; demultiplexing the
multiplexed bit stream in the receiver equipment for producing a stream
of serial signaling bits; determ;nlng whether the most recently received
2s N signaling bits in the serial signaling bit stream match with one of the
N-bit patterns of the primary and secondary code words during each
--2--
D-24,717
2~
signaling bit interval; producing during each signaling bit interval a
first indication that the selected and transmitted signaling state is a
prescribed signaling state Sp when there is a match between the most
recently received N signaling bits of the serial signaling bit stream and
one of the N-bit primary and secondary code words associated with the
prescribed signaling state Sp; and producing during each signaling bit
interval a second indication that is the same as the preceding first
indication when there is not a match between the most recently received N
signaling bits of the serial signaling bit stream and any of the primary
and secondary code words.
In accordance with another aspect of this invention apparatus for
performing asynchronous signaling in a digital communications system
including transmitter and receiver equipment for multiplexing and demulti-
plexing dig1tal signaling information signals and digital traff;c informa-
tion signals, each of the signaling information signals defining a differ-
ent one of a plurality of signaling states Sl-SM, comprises means for
storing a plurality of M unique N-bit primary digital code words Sml each
defining a different one of the signal states Sl-SM and each having N-l
addition~l ordered permutations of the order of the N-bits thereof, with
the additional ordered permutations being designated as secondary code
words; first means responsive to a particular status/control input signal
for causing the storing means to serially produce an output signal
comprising serial bits Bl-BN of one of the primary and secondary code
words for a particular signaling state Ss at a signaling clock rate;
means for multiplexing the serially produced bits from the storing means
with traffic information bits at signaling time slots in a bit stream
when the signaling time slots occurring at the signaling clock rate;
means for transmitting the multiplexed bit stream to receiver equipment;
--3--
D-24,717
~3~
means for extracting a signaling clock signal from the multiplexed bit
stream in the receiver equipment; means for demultiplexing the multiplexed
bit stream in the receiver equipment for producing a stream of serial
signaling bits; and means For producing during each signaling bit interval
a first indication that the transmitted signaling state is a prescribed
signaling state Sp when there is a match between the most recently re-
ceived N signaling bits of the serial signaling bit stream and one of the
N-bit primary and secondary code words associated with the prescribed
signaling state Sp; and producing a second indication when there is not a
match between the most recently received N signaling bits of the serial
signaling bit stream and any of the primary and secondary code words.
DESCRIPTION OF THE DRA~INGS
FIG. 1 is a tabulation of signaling states and associated digital
code words.
FIG. 2 is a schematic block diagram of a transmitter of a digital
communication system embodying this invention.
FI&. 3 is a schematic block diagram of a receiver in a digital
communication system embodying this invention.
FIG. 4 is a flow diagram for a microcomputer embodiment of decoder 55
and latch circuit 65 in FIG. 3.
FIG. 5 is a tabulation illustrating the operation of the decoder 55
and latch 65 in FIG. 3 for the converter 23 switching From transmitting
an S31 to an S41 code word at the end of S31.
FIG. 6 is a tabulation illustrating the operation of the decoder 55
and latch 65 in FIG. 3 for the possible transient sequences that may
occur in switching from transmitting an S3 to an S~ signaling state.
--4--
D-24,717
~23~
FIG. 7 is a tabulation illustrating the operation of the decoder 55
and latch 65 in FIG. 3 for the converter 23 switching from transmitting
an S41 to an S31 code word at the end of S41.
FIG. 8 is a tabulation illustrating the operation of the decoder 55
and latch 65 in FIG. 3 for the possible transient sequences that may
occur in switching from transmitting an S4 to an S3 signaling state.
FIG. 9 is a schematic block diagram of an alternate embodiment of
this invention.
FIG. 10 is a flow diagram for a microcomputer implementation of the
decoder logic 55 and latch circuit 65 together with the integrator 75 ln
FIG. 9.
FIG. 11 is a tabulation illustrating the operation of the decoder 55,
latch 65 and integrator 75 in FIG. 9 for the converter 23 switching from
transmitting an S41 to an S31 code word at the end of S41.
FIG. 12 is a tabulation illustrating the operation of the decoder 55,
latch 65 and integrator 75 in FIG. 9 for the possible transient sequences
that may occur in switching from transmitting an S4 to an S3 signaling
state.
DESCRIPTION OF PREFERRED EMBODIMENTS
It is known that N-binary bits map out 2N digital N-bit words.
Although each of these N-bit words is different, only some of them are
unique such that cyclically changing the order of the bits of one unique
word will not produce a different unique word. Stated differently, each
adjacent N-bits out of two identical back-to-back N-bit words that define
~he same unique word will not define a different unique word. Rather the
N-bit words, called code words, from the back-to-back pair thereof are
--5--
D-24,717
ordered permutations of the same ordered group of N-bits where one of
them is called a primary code word that is identified with the unique
word and the others are called secondary code words. By way of example,
for N=2, the 2N=4 two bit digital code words are A=OO, B=Ol, C=10 and
5 D=ll. Two pairs of these words taken back-to-back are AA=OOOO and
DD=llll. Considering these pairs of code words 2-bits at a time (e.g.,
with a 2-bit window that moves from left to right) it is seen that both
00 and 11 are unique and primary code words since permutations thereof do
not produce other ones of the code words of A-D. Considering pairs of
the other two code words (BB=O101 and CC=1010 ) with the 2-bit moving
window, however, reveals that 01 and 10 are ordered permutations of the
same unique code word. Thus, only one of these digital words B and C can
be considered to be a unique digital word. By way of example, B is the
unique state or word with 01 being the primary code word and 10 being the
15 secondary code word. It can be readily determined that for N=5 that
there are 8 unique states, 6 of which have 5 entirely different permuta-
tions. Similarly, for N=5 there are only 14 unique states, with 9 of
them each having 6 entirely different permutations.
FIG. 1 is a tabulation of 5 unique signaling states Sl-S5 which are
20 defined by associated N=6 bit primary code words Sll-S51 in column 2.
There are 6 different ordered permutations of each of these primary code
words. The ordered permutated code words are defined in column 3 by
legends where the first and second numbers following the letter S
describe the particular signaling state ~or unique word) and an associated
25 ordered permutation, respectively. The code words in which the second
number is a 1 are referred to as primary code words. The code words in
which the second numeral is other than a 1 are referred to as secondary
code words.
--6--
D-24,7l7
3~
In regard to FIG. l the number of possible signaling states and the
number of signaling bits thereof are dependent on the degree of error
protection or robustness required in the system. The technique can be
optimized for minimum transition to transition differential delay for
5 applications where pulse distortion is undesirable. More specifically,
the signaling code words are chosen so that in cases where a constant
reaction time is desired when switching between two states, e.g., to
conserve symmetry so as to minimize pulse distortion, then approximately
the same number of signaling bit intervals occur before a transition is
complete when changing from state X to state Y as occur when changing
from state Y to state X. This will be illustrated subsequently by the
tabulations in FIGs. 5 and 6. Additionally, adjacent signaling words are
chosen so that hybrid words or combinations of N-bits of two adjacent
code words which occur during any possible transition preferably are not
the same as other defined code words and are therefore to be decoded as
invalid states. And for the code words illustrated in FIG. l the 6 bits
representing the signaling states are chosen to have Hamming distances of
two, so that signal errors will preferably not cause an indication of
unintended signaling states, where the Hamming distance is the number of
20 digital positions in which the corresponding digits of two binary words
of the same length are different.
A digital communication system for practicing this invention generally
comprises transmitter and receiver circuitry that is illustrated in FIGs.
2 and 3, respectively. Signaling equipment in the transmitter includes a
signaling logic circuit lO, a ccde word generator l6, and a parallel to
serial converter 23. Serial signaling bits on line 24 from the converter
are multiplexed with data-information bits on line 25 in the conventional
manner in the circuit 26 and transmitted to receiver circuitry such as by
--7--
D-24,717
~L~3 ~ 6~
radio, cable or a satellite system. Signaling circuitry in the receiver
equipment comprises circuitry 35 for extracting signaling clock informa-
tion from the multiplexed bit stream on line 34, a demultiplexer circuit
40 for extracting signaling bits from the multiplexed data stream, an
N-bit serial shift register 45 that receives the serial signaling bits on
line 41 and has N output lines which drive decoder logic circuit 55, and
a latch circuit 65 that is driven by outputs of the decoder logic.
In operation, transmitter equipment (not shown) applies signaling
and/or control type information to logic circuit 10 and generates a
traffic-data signal on line 25 in the conventional manner. In a satellite
pulse code modulation (PCM) communication system embodying this invention
that was built and satisfactorily operated each frame was made up of 100
bits with the 26th and 76th bits thereof carrying signaling information.
The first bit of each frame was a framing synchronization bit. The
system had a 33 1/3 KBPS pulse rate. The signal on line 25 was a 32 KBPS
encoded digitized voice signal. No special consideration of the signaling
format is required other than to insure that signaling bits not simulate
the framing bit sequence.
The logic circuit 10 is operative for continuously producing a binary
1 on a selected one of the lines 11-15 for indicating that the current
status and control type information on lines 8 corresponds to an assigned
one of the signaling states Sl-S5 in FIG. 1. The signaling states Sl-S5
may by way of example correspond to signaling conditions of ring received,
network seizure, reverse battery, loop-back, and no input activity. Thus,
2s in this example the equipment in FIG. 2 is at a central office.
The generator 16 is responsive to a binary 1 on the selected one of
the lines 11-15 for continuously producing an assoclated N=6 bit primary
--8--
D-24,717
~ 3~
code word on lines 17-22 ,i.e., it is present on lines 17-22 during each
signaling bit interval. In a preferred embodiment the generator 16
comprises a memory such as an EPROM containing look-up tables storing the
primary code words Sll-S51. The code word on lines 17-22 changes whenever
there is a change in the signaling state from logic circuit 10. The
counter means 31 is periodically incremented by signaling clock pulses on
line 7 and is selectively triggered by a framing pulse (e.g., at the
first bit of each frame) on line 5 for producing a load pulse on line
32. More specifically, circuit 31 is responsive to the framing pulse on
line 5 that follows every sixth signaling clock pulse on line 7 for
producing a control pulse on line 32 which enables converter 23 to sample
the code word on lines 17 22. The converter 23 is conventional and oper-
ates at the signaling clock rate for reading out the 6 bits stored therein
as a serial bit stream on line 24 with the bit Bl being outputted on line
24 prior to the bit BN=B6. The multiplexer 26 interleaves the signaling
bits with data bits on line 25 in the conventional manner to form the in-
terleaved bit stream on line 27 which is transmitted to receiver equip-
ment.
As will be apparent from the following description, the specific
application in which this signaling technique is used may impact on the
selection of particular code words and the manner in which the trans-
mitter changes from outputting one signaling code word on line 24 to
outputting another signaling code word there. More specifically it is up
to the system designer to determine how the converter 23 will respond to
a change in the signaling state from logic circuit 10. The cleanest
method of transmission is to have converter 23 output all N=6 bits of a
primary code word onto line 24 before converter 23 samples the next
primary code word on lines 17-22, i.e., to transmit a different signaling
_g_
D-24,717
~ 3 ~
state only at the end of a group of 6 signaling clock pulses on line 7.
This is readily accomplished by making the detector 29 insensitive to a
change of signaling state on the output of logic circuit 10. Detector 29
will therefore have no effect on the operation of counter means 31. It
may be desirable in some instances to immediately change from transmitting
one primary code word to another primary code word in order to save time.
This is readily accomplished with circuit 29 which detects a change in
signaling state on lines 11-15 and produces a control pulse on line 30.
This causes circuit 31 to produce a load pulse which enables converter 23
to immediately start outputting the new code word. Alternatively, circuit
29 can operate for causing the converter to immediately change to transmit
a new code word for only some signaling states.
The receiver circuit 35 in FIG. 3 extracts the signaling clock from
the multiplexed bit stream 34 which is then passed on line 37 to demulti-
plexer 40. The circuit 40 separates the s~rial signaling bits from thedata stream for producing a continuous stream of signaling bits on line
41 at the signaling clock rate. The signaling bits are shiFted through
register 45 at the signaling bit rate, with an indication of the oldest
and most recent signaling bits in register 45 be;ng available on lines 46
20 and 51, respectively.
The decoder logic 55 includes a memory which stores all of the code
words that can be produced by generator 16 and all sf the ordered per-
mutations thereof. These stored code words are called valid or allowable
states or allowable code words and may by way of example correspond to
the group of code words in FIG. 1. Thus, if there are M states that are
each identified by an N-bit word then there are normally MN possible
valid code words or valid ordered combinations of signaling bits. The
circuit 55 is operative for determining whether the current N bit word in
--10--
D-24,717
9L~3tL~
register 45 is one of the allowable code words or is an invalid word
which does not correspond to an allowahle state. When the contents of
register 45 corresponds to a val;d code word the decoder circult 55
produces a binary 1 on a selected one of the output lines 56-61 and a
binary 0 on the other of the lines 56-61 and 62. Conversely, when the
contents of register 45 corresponds to an invalid code word the decoder
logic produces a binary 0 on lines 56-61 and a binary 1 on the output
line 62.
The latch circuit 65 is periodically enabled by the signaling clock
for reading the output signals Dl-D5 from the decoder 55. If a current
one of the output signals Dl-D5 is high, then the associated one of the
output signals Ql-Q5 also goes high to indicate that the current trans-
mitted code word corresponds to a selected one of the signaling states
Sl-S5, respectiYely. If the decoder output signal on line 62 is high
(for indicating that the current contents of register 45 corresponds to
an invalid code word), however, latch circuit 65 is inhibitQd from read-
ing the output slgnals Dl-D5 (which are all low at this time). Instead
the latch makes the one of the output signals Ql-Q5 thereof high that was
previously high for indicating that the current transmitted code word is
the same as the transmitted code word occurring during the previous N
signaling time intervals. Thus, the last valid input state from the
decoder 55 is latched at the output of the latch circuit 65 whenever an
invalid word is indicated on line 62. This state could be caused by
errored bits or by transient states or combinations of bits that occur
when the transmitter changes state. The latch circuit will also latch up
to produce the previous output signal thereof whe~ the logic levels on
all of the lines 56-62 are low. With this receiver process the signaling
integrity is enhanced by essent;ally precluding incorrect changes in the
-1 1 -
D-24,717
~3~
latched signaling output state unless two or more errors of the basic
signaling block repeat consistently.
The shift register 45, decoder circuit 55 and latch circuit 65 may be
a custom designed circuit, be implemented with discrete logic elements or
be implemented with digital computer circuitry. In a preferred embodiment
of this invention that was built and operated the register 45, decoder 55
and latch circuit 65 were all implemented on a Model 8039 microcomputer
manufactured by Intel corporation which was also utilized for performing
other functions in the digital communication system. A flow chart defin-
ing the softs~are program for making the microcomputer perform the pre-
scribed functions of the decoder 55 and latch circuit 65 is shown in FIG.
4. The loop defined by boxes 103-108 in FIG. 4 is repeated continuously
for each signaling bit interval, until it exits to either step 111 or
step llS.
It is clear that if generator 16 continuously produces the same pri-
mary code word on lines 17-22 then the output of latch circuit 65 will
indicate the same code word for each sampling interval, assuming there
are no errors in transmission such as are caused by noise. It can read-
ily be seen, however, that different combi~ations of bits will occur dur-
20 ing the N-bits following a transition between signaling states, i.e.,
after converter 23 stops outputting one primary code word and starts a
different primary code word. The tabulation in FIG. 5 illustrates the
operation of decoder circuit 55 and latch 65 in FIG. 3 when converter 23
changes from transmitting a primary code word S31 to outputting a primary
code word S41 at the end of transmission of the code word S31 by converter
23, i.e., after a group of six signaling clock pulses on line 7. The
second column in FIG. 5 is essentially what is seen by viewing row 1 of
column 2 with a moving 6 bit windos~ that moves from left to right by one
-12-
D-24,717
~ 23~
bit for each signaling interval. More specifically, at signaling time
interval t=l the decoder 55 tries to match the contents of register 45,
consisting of one bit of the new word S41 and N~l bits of previous code
word S31, to its repertoire of valid signaling code words. During the
next signaling bit interval at t=2, the decoder 55 tries to match the
N-bit word comprising the first two bits of the new code word S41 and N-2
bits of the previous code word S31 with the valid code words that are
stored thereby. This operation is repeated during each signal bit with
the N-bit window advanced in this manner during each signalling bit
o interval. Column 3 reveals that at signaling times t=l and t=5 the
contents of register 45 correspond to an invalid code word (represented
by the symbol 0) such that the latch 65 repeats the previous output
therec,f for indicating that there has not yet been a change in the
signaling state at the transmitter. In this instance it is on1y after
receipt of the new primary code word in register 45 that latch 65
indicates that a code word designating the signaling state S4 is now
being transmitted.
Each row of the tabulation in FIG. 6 illustrates an operation similar
to that in FIG. 5 where the converter 23 is caused to change from output-
ting the primary code word S31 to outputting the new primary code wordS41 for the signaling state S4 during different time slots. Stated dif-
ferently, FIG. 6 illustrates the operation of the decoder 55 and latch 65
in FIG. 3 when converter 23 terminates generation of the primary code word
S31 after only shifting some of the bits of the code word S31 through it
prior to its sampling and abruptly switching operation to outputting the
new primary code word S41.
D-24,717
The tabulations in FIGs. 7 and 8 illustrate similar operations of the
decoder 55 and latch 65 in FIG.3 when generator 16 switches or moves in
the opposite direction for switching from transmitting the primary code
word S41 to outputting the primary code S31 on llnes 17-22. In this
instance it will be noted that the incorrect but valid code word S2 is
recognized by the decoder and outputted by the latch circuit at times t=2
and t=5 in FIG. 7. Additionally the incorrect but valid code word for
signaling state S5 can be recognized by decoder 55 and passed by the
latch circuit 65 in FIG.3 for the back-to-back signaling states S43 and
S31 in row 3 of the tabulation in FIG. 8. It is desirable therefore that
primary code words be chosen such that groups of N=6 bits out of pairs of
code words will not make up hybrid words defining valld but incorrect
signaling states that are the same as these and other primary control
words or ordered permutations thereof during all possible transitions
between signaling states. Such a selection of primary code words will of
course depend on the particular application for this signaling techniques
In an application where minimum asymmetry is desired the appearance of a
signaling state S2 in FIG. 8 would be defined as an invalid state thus
demonstrating the flexibility of the technique. This can be accomplished
20 with an integrator circuit as is described more fully hereinafter or with
programming in a software implementation of the decoder 55. Comparison
of the tabulations in FIGs. 6 and 8 also reveals that the output of de-
coder 55 changes state after 5 or 6 signaling intervals for a state S3 to
a stated S4 transition whereas it changes state after 5, 6 or 7 intervals
for a state S4 to a state S3 transition tassuming the indication of a
signaling state S2 is invalid). Thus, the worst case asymmetry provided
in this example is 2 signaling bit intervals.
-14-
D-24,717
23~6~
An alternate embodiment of this invention that overcomes the afore-
mentioned problems is illustrated in FIG. 9 and comprises an integrator
type of memory device 75 that is inserted between the decoder logic 55
and the latch circuit 65 for effectively isolating the latch circuit from
false indications of transmitted signaling states that may be produced by
the decoder logic. The integrator circuit 75 essentially causes the
latch circuit 65 to produce an output indicating that the transmitted
code word in the register 45 is the same as the previously transmitted
code word for at least P consecutive signaling bit intervals following
receipt of an invalid code word. With the memory circuit 75 a change of
state at the output of the latch will only occur if P consecutive groups
of N signaling bits are each decoded as the same new valid code word or
signaling state. More specifically, the same output of decoder 55 must
be maintained throughout P consecutive signaling time slots to enable an
associated AND-gate and trigger the latch circuit 65 so as to produce a
new output signal on a different one of the output lines 66-71 of the
latch circuit. A flow chart for implementing the functions of the FIG. 9
circuit on the microcomputer is shown in FIG. 10. The tabulations in
FIGs. 11 and 12 illustrate the operation of the decoder 55, integrator
75, and latch 65 for these same combinations of or sequences of code
words as are illustrated in FIGs. 7 and 8 when the memory circuit or
integrator 75 is connected in series in the lines 56-61 with P=5. In
these instances it is seen that although the decoder circuit 55 correctly
recognizes the code words for incorrect but valid signaling states S2 and
2~ S5, the memory circuit 75 requires the latch circuit 65 to continue to
produce an output indicating that the current transmitted signaling state
has not yet changed. Thus, a change of state from a latched output
signaling state will only occur if N consecutive signaling b;ts are
-15-
D-24,717
~L2 3~
decoded as a consistent valid state for P consecutive signaling bit
intervals. The circuit 75 merely introduces a delay of P signal1ng clock
intervals before a new signaling state is indicated at the output of the
latch circuit. This delay may be varied for improving the integrity or
reliability or non-susceptibility of the system to noise.
Errored bits cause a delay in the latch output refresh if the error
occurs during a period of unchanging transmitter state; or a delay in the
change of state from the latch outputs if the error occurs during a
transmitter change of state sequence. The effect should be at worst a
o distortion of N-bit intervals in the timing of the receiver output change,
but an incorrect received output state cannot occur unless enough errors
occur to exceed the Hamming distance of the transmit words. So, identical
double error pairs that are separated by N signaling bit intervals are
necessary to cause a decoder output error.
Stated differently, if a signaling bit is received in error the
decoder logic will register an "Invalid ~ord" while the errored bit is
shifted through the Receive Shift Register, unless the error causes
another valid word to be simulated. The probability of this happening
depends on the choice of transmitted words. If they are chosen to have a
minimum Hamming distance of H, then H or fewer errors in any N contiguous
bits received will not simulate another transmitted state but will cause
the latching circuit to freeze its output for N-bit intervals. This
action can cause delay during a change of signaling state, but should not
cause unintended receiver output states. If H bits or more are in error
in N contiguous bits, the probability of simulating another valid word
can be calculated from an analysis of the various ways that the errors
can occur and the repertoire of valid received words.
-16-
D-24,7l7
Although this invention is described in relation to preferred
embodiments thereof, variations and modifications are possible. By way
of example, the traffic may be digitized voice in a PCM system or pure
data information. Also, the system can have different framing formats
from what is described here. Additionally, the generator can output
either primary or secondary code words. Further, the circuits l6, 23, 29
and 3l can also be implemented with a microcomputer. The scope of this
invention is therefore to be determined from the attached claims rather
than from the aforementioned detailed descriptions of preferred embodi-
~o ments.
-l7-