Method and Apparatus for the Channelized Serial Transmission of Redundantly Encoded Binary Data

The invention relates generally to the transmission of pulse code modulation (PCM) information on fiber optic transmission facilities and more particularly to a method of redundantly encoding binary words into encoded binary words as well as circuits for achieving the encoding and decoding functions and for communicating the encoded binary data.

It is generally known that it is desirable to transmit data on fiber optic transmission facilities using binary data as opposed to, for example, bipolar data becauses it simplifies the design of the optical transmitter and receiver circuits which can then operate in a simple ON-OFF manner. However, in order to allow synchronous recovery of the data at the receiver, the raw binary data must be encoded in a way that provides sufficient edges to allow extraction of the clock at the receiver.

A further requirement of binary data transmission is that the signal should be at least approximately balanced; that is, that it should contain an approximately equal number of one and zero pulses. This helps to keep the receiver amplifier design simpler by allowing AC coupling. It also means that the average power transmitted is constant at one-half peak power thereby making it possible to achieve a higher peak power for an LED or laser driver without exceeding its specifications. It is also desirable that the transmission scheme provide for detection of transmission errors.

Since contemporary telecommunication systems handle voice and data information in digital form, the information is usually handled in blocks or channels. For example, one such digital system presently in use throughout North America deals in 10-bit channels each comprising an 8-bit PCM sample, a signalling bit and a parity bit. Thus, the invention is directed to a method for the block redundant encoding of binary data to a form suitable for the transparent transmission of such binary data on a fiber optic transmission line and the circuits for translating the binary data to encoded binary data and vice-versa.

The known systems for the redundant encoding of binary data are either not suitable for the channelized serial transmission of PCM binary data or they suffer from one or more major problems in the realization of the function.

One such system is described in U.S. patent application No. 626,895 by W. D. Grover, filed on July 2, 1984 and assigned to the present assignee. It describes a method of communicating redundantly encoded binary data on a fiber optic transmission facility. The n-bit binary data is encoded into m-bit binary data using a read-only-memory (ROM). The ROM contains 2.sup.m binary words that have been partitioned into sets of words that reflect predetermined criteria for run-length. The n-bit words are translated into corresponding m-bit binary words using pairs of selected sets from the translation tables in the ROM to provide a DC balanced signal on the transmission line. Frame synchronization of the data is achieved by translating the n-bit words into m-bit binary words using predetermined different sets of data from the translation tab1es in the ROM. A receiver is adapted to recognize the framing information by recognizing the translation sets from which the m-bit words were derived. One or more of such m-bit words are used to confirm synchronism between receiver and transmitter. Although such a system functions adequately under some circumstances, the robustness of the synchronization scheme is not acceptable under other circumstances.

Accordingly, it is an object of this invention to provide a system for the communication of redundantly encoded binary data which exhibits robust synchronization characteristics.

It is another object of the invention to provide a method for encoding a set of 2.sup.n binary words into a set of 2.sup.m binary words, wherein m>n and wherein the two sets of words exhibit mutual x invariant bits thereby minimizing the size of the translation table. The size of the translation ROM is also minimized by mapping the remaining m-x bits of the linecode words to the n-x bits of the binary words. The redundant binary code generated by the method of the invention also provides the DC balance characteristics and inherent clock information desirable for binary data transmission.

In accordance with the invention, there is provided a method of redundantly encoding a set of 2.sup.n binary words into 2.sup.m encoded binary words wherein m is greater than n. The method comprises the step of selecting from the set of 2.sup.m words, a first subset of words comprising one m-word for use as a synchronization word (sync-word) and its m distance-one neighbors. The sync-word is selected to meet predetermined criteria for internal maximum run-length of one-bits and DC balance. A second subset of words meeting predetermined criteria for head maximum run-length, tail maximum run-length and overall internal maximum run-length of one-bits is also selected from the set of 2.sup.m words; this subset excludes the first subset of words. A third subset of words is then generated by eliminating from the second subset of words all m code words which could produce a non-aligned code word corresponding to any one word from the first set of words across channel boundaries. A fourth subset of words which provide x invariant bits between themselves and the words of the set of 2.sup.n binary words is then selected from the third subset of words. Each of the words from the fourth subset of m words may then be assigned to one word of the set of 2.sup.n binary words so that the m-x bits of the fourth subset of words map uniquely to the remaining n-x bits of the words in the set of 2.sup.n binary words.

The resulting mapped sets provide a translation table whose encoded binary words exhibit all the desired characteristics for transmission as well as a sync-word which lends itself to a robust synchronization scheme. The sync-word is instantly recognizable at the receiver; it is also at least a two-bit error away from any other encoded word and it cannot be mimicked by an inter word sequence of encoded words.

Also in accordance with the invention, there is provided a circuit for the translation of a set of 2.sup.n binary words into redundantly encoded binary m-words. There is provided a plurality n of input terminals and a plurality m of output terminals as well as a means for storing a plurality of m-words generated in accordance with the method described above. The storing means is responsive to any one of 2.sup.n words appearing on the input terminals for outputting a predetermined one of the encoded words. The storing means has n data inputs, each one connected to a respective input terminal and only m-x data outputs wherein x represents the number of invariant bits between the n-bit words and the m-bit words. The m-x data outputs of the storing means are connected to predetermined respective ones of the output terminals and the inputs of the storing means corresponding to the x bits are connected to the remaining output terminals through respective transmission gates. A plurality m of transmission gates have their outputs connected to respective ones of the output terminals and their inputs connected to respective sources of ONE or ZERO levels wherein the pattern of ONEs and ZEROs define a predetermined special code word. A special-word select circuit is responsive to a control signal for inhibiting the output of the storing means and the x-invariant transmission gates and for enabling the plurality of transmission gates thereby to cause the predetermined special code word to appear on the plurality of output terminals.

Also in accordance with the invention there is provided a circuit for the translation of encoded binary m words into 2.sup.n binary words. The circuit comprises a plurality m of input terminals and a plurality n of output terminals as well as a ROM for storing a plurality of n-x bit words generated in accordance with the method of the invention. The ROM is responsive to the m-x bit portion of the m-bit words appearing on the input terminals for outputting a predetermined n-x bit portion of the n-bit word on the output terminals. The x bits of the input m words are bypassed around the ROM and appear unchanged on the output terminals. The ROM may also provide identification of special flag words as well as error indications of invalid linecode words received at the input terminals.

The encoding method of the invention thus permits the realization of a transmission system for channelized redundantly encoded binary data which exhibits robust synchronization between receiver and transmitter and which requires translation table storing means of greatly reduced size. The invention also provides a measure of error detection for the received data .

An example embodiment of the invention will now be described with reference to the drawings in which:

FIGS. 1A, 1B and 1C comprise a flow chart depicting a method of redundantly encoding binary data in accordance with the invention;

FIG. 2 is a block logic diagram of a circuit for translating binary data into redundantly encoded binary data in accordance with the method of the invention;

FIG. 3 is a block logic diagram of a circuit for translating redundantly encoded binary data into binary data in accordance with the method of the invention;

FIG. 4 shows an alternate logic circuit for performing the function achieved by the circuit of FIG. 3; and

FIG. 5 is a block circuit diagram of a transmission system for transmitting redundantly encoded binary data in accordance with the invention.

In order to clarify its description the invention will be described in the context of a system using a transmission frame of five hundred and twelve channels each comprising ten bits partitioned as eight-bit PCM, one parity bit and one signalling bit. This binary data is to be redundantly encoded to twelve-bit words for transmission on a fiber link and decoded to ten-bit data at a receiver.

FIG. 1 depicts the method used to encode a possible 2.sup.n binary words into m words where n=10, m=12, and the m words exhibit predetermined characteristics as described above and as set out in the first block of FIG. 1A.

Since only a fraction of the possible m-bit code words (4096) is needed for transmitting n-bit data (1024 words), some of the remaining valid codewords can be used for error detection, frame synchronization and indication of special link conditions or alarms. In the system of the invention, the derived set of linecodes lends itself to the use of all three of these possibilities. The unused or illegal bit patterns may be detected at the receiver and counted to give an estimate of the link bit error rate for maintenance purposes. A special twelve-bit SYNC codeword, not included in the set of 1024 codewords used for coding data is generated periodically at the transmitter and detected at the receiver to establish and maintain channel boundaries. It is also used to obtain PCM frame timing by indicating the position of channel 0. This method has the effect that synchronization is achieved instantly. The scheme of using a special SYNC word for synchronizing channels and frame boundaries requires not only that the SYNC word be different from data codewords, but also that it cannot be simulated in any non-channel-aligned window over adjacent data codewords. It is further desirable to make the scheme as robust as possible by choosing a SYNC code which is tolerant of bit errors.

A method of generating the desired codeword set as depicted in FIG. 1 will now be described. The principle of the code set generation is to start with the full set of 4096 code words and then successively eliminate codewords that do not meet predetermined criteria. Practically, the desired sets of data are obtained by performing a number of recursive interactive steps on the full set of 2.sup.n words using a general purpose computer. If the remaining set contains at least 1024 code words divided into 16 subsets of 64 code words each, a useable code set has been found.

Step 1

From the set of 2.sup.m binary words, select all the m words meeting predetermined criteria related to weight and run-length. In this example, the minimum and maximum weight of the words was set at 5 and 7 respectively in order to achieve a statistically DC balanced transmission of weight.apprxeq.6. The maximum run-length internal to a code word was set at 4, the maximum run-length at the start or head of a code word was set at 2 and the maximum run-length at the end or tail of a code word was also set at 2. This combination of maximum intra, head and tail run-lengths ensures that a run-length of 4 is never exceeded regardless of the data sequence.

Step 2

From the set of 2.sup.m words identified in step 1, select a SYNC word having the predetermined weight as well as meeting the predetermined criteria for head and tail run-lengths. The m(12) distance-1 neighbors (forbidden code words) of the SYNC word are then identified. In this example embodiment, the SYNC word was finally selected to be 782 in hexadecimal.

Step 3

Eliminate from the candidate set generated in step 1 all code words which are equal to the forbidden set or which could produce a non-aligned forbidden code word across channel boundaries. This procedure ensures that a sequence of valid code words will not contain a 12-bit sequence anywhere in a serial data stream that will equal or resemble (to within one bit) the SYNC code. A 12-bit code is accordingly eliminated if it meets any of the following tests:

first 11 bits of C=last 11 bits of Fi

first 10 bits of C=last 10 bits of Fi

first 9 bits of C=last 9 bits of Fi

first 8 bits of C=last 8 bits of Fi

first 7 bits of C=last 7 bits of Fi

first 6 bits of C=last 6 bits of Fi

last 7 bits of C=first 7 bits of Fi

last 8 bits of C=first 8 bits of Fi

last 9 bits of C=first 9 bits of Fi

last 10 bits of C=first 10 bits of Fi

last 11 bits of C=first 11 bits of Fi

all 12 bits of C=all 12 bits of Fi

where:

C=code word to be tested

F (i=1 to 13)=forbidden set of code words.

If this elimination step results in less than 1024 code words in the candidate set, another SYNC word must be selected and the procedure repeated until at least 1024 code words are identified.

Step 4

A set of code words that provide x invariant bits between the n-bit words and the m-bit words selected above may then be identified. In this embodiment x=4 was selected.

For all possible combinations of x bits out of the 12 bits, partition the words of the candidate set into 2.sup.x =(16) possible subsets of at least 2.sup.(10-x) =(64) members such that each subset contains the code words of the candidate set which have the same values in the x bits. The resulting subsets provide the required information for drawing up a translation table wherein x bits of the 12-bit code words are equal to x bits of the 10-bit code words. With x=4 this means that an 8-bit wide translation table is sufficient for the encoder. Generally, the table must still contain 1024 entries because the remaining bits in each of the 16 subsets may not be equal across subsets. The candidate set of code words identifies the position of the 4 invariant bits in the 10-bit to 12-bit mapping.

Step 5

In this example embodiment, the previous step provided a candidate set containing a total of 1183 valid code words comprising 239 different 8-bit patterns. The 16 subsets of 8-bit words are not equal but they are redundant to the extent that most subsets contain more than the minimum 64 members. It is then possible to select 12-bit to 10-bit mappings such that not only 4 bits are invariant but that the remaining 8 bits of the 12-bit code words map uniquely to the remaining 6 bits of the 10-bit data words. The 4 invariant bits are given by the subset identifier and the remaining 8 bits form words to be decoded into 6-bit words by a translation ROM. The 6-bit decode words can then be assigned arbitrarily to 8-bit words as follows. If the same 8-bit value exists in every subset, it is assigned and removed from the list. If two or more 8-bit values exist such that all 16 subsets are covered but each subset contains only one of the two or more values tested, then these values are assigned to one 6-bit decode word and removed from the list. Of the 8-bit values left on the list, combinations are selected as just described but multiple occurrences across subsets are permitted.

This sequence of operations assigns to each of the 64 possible 6-bit decode values one or more 8-bit values without duplication. This ensures uniqueness of decoding and permits the use of a 256.times.6-bit decoding ROM instead of a 4096.times.6-bits ROM (assuming 4 invariant bits).

After the 1024 data code words are selected from the set of valid 12-bit code words, a number of codes may be left over as spares which may be used to implement out-of-band flags. These can be sent in place of data, decoded instantly at the receiving end, and may be used to indicate alarm conditions or to control maintenance functions. The following 15 special or flag code words have been selected in this embodiment because they are easily recognized with the decode ROM (as described later) which only looks at 8 bits of the linecode. The codes are listed in hexadecimal.

The 1024 translation words used in the described embodiment of the invention are listed in TABLE I at the end of disclosure. The listing is in hexadecimal; the first column lists 10-bit code words and every row lists one 10-bit word together with its corresponding and ensuing seven 12-bit words. The SYNC code selected in this embodiment was H782.

FIG. 2 illustrates a circuit for encoding 10-bit data words into 12-bit data words in accordance with the method described above. A ROM 20 is adapted to contain a 1024.times.8-bit translation table as described above. The 10-bit data words are applied to input terminals 21 which are connected to corresponding inputs of the ROM 20. The outputs of the ROM are each connected to predetermined ones of output terminals 22. The input terminals 21 (0, 1, 8, 9) corresponding to the 4 invariant bits are connected to output terminals 22 (1, 3, 7, 11) through transmission gates 23. A plurality of transmission gates 24 have their outputs connected to respective ones of output terminals 22 and their inputs connected to a source of data. The sequence of bits on the inputs of gates 24 represent a special 12-bit code word which as described above could be the SYNC word or one of the special control words. A special-word select circuit 25 is responsive to a control signal from, for example a controller, for inhibiting the output word from the ROM and the outputs of gates 23 via lead 26. The circuit 25 is also responsive to the control signal for enabling the appearance of a special word connected to the inputs of gates 24 on the output terminals 22.

As indicated above, the position of the invariant bits in the 12-bit code is given from the construction of the code set; however, their allocation in the 10-bit code can be chosen freely. In this case, the choice was made on the basis of minimum impact of errors. The other six data bits appear on the linecode in the eight code bits which are not invariant. Thus, line errors affecting these bits potentially cause a change in none, some, or all of the six data bits after decoding. On the average, it may be expected that a single such line error will cause multiple data errors (within the same byte). Line errors affecting the invariant bits however do not get multiplied by the decoding and are directly propagated to the output. Therefore, for a given error rate, the four invariant bits will on average exhibit fewer data errors than the other coded bits. Thus, the invariant bits should be allocated to the bits representing the more critical information. In this case, the four invariant bits are allocated to bits 0, 1, 8, and 9 of the 10-bit data words. These bits correspond respectively to the parity bit, signalling or control bit, the most significant bit and sign bit of the PCM byte.

FIG. 3 shows a decoder circuit for decoding 12-bit linecode into 10-bit binary words. A ROM 30 adapted to contain 256.times.8 bits has its 8 inputs (A0-A7) connected to the input terminals 31 (0, 2, 4, 5, 6, 8, 9, 10) corresponding to the bits in the 12-bit code words that are not invariant. The outputs (D0-D5) of the ROM 30 are connected to the output terminals 32 (2, 3, 4, 5, 6, 7) corresponding to the bit positions in the 10-bit words that are not invariant. The input terminals 31 (1, 3, 7, 11) bypass the ROM 30 and are connected directly to the output terminals 32 (0, 1, 8, 9) that correspond to the invariant bit positions in 10-bit words. Whenever the ROM 30 recognizes a special control word, it outputs a signal on terminal D6 to set a flag register 33. The identification of the control signal is represented by the sequence of bits from the outputs D0-D3 of ROM 30; these are available from output terminals 32 (2, 3, 4, 5).

Whenever the ROM 30 detects an invalid input code, it outputs an error signal on terminal D7 to an error register 34 via an OR gate 35. Similarly logic gates 36, 37, and 38, 39 are connected to the input terminals 31 at bit positions 0, 1, 2 and 9, 10, 11 to detect violations of the predetermined criteria for head and tail run-lengths of the encoded 12-bit binary words.

The redundancy inherent in 10-bit-12-bit code provides a certain amount of error detection capability that is theoretically limited to the extent to which errors transform valid code words into invalid code words (50%). The detection capability is reduced further if the decoder implementation does not perform a complete test of validity. In the circuit of FIG. 3, the data decode ROM which converts the eight varilant bits to six data bits can only detect seventeen invalid 8-bit combinations. The separate additional logic circuit comprised of gates 35 to 39 detects all errors indicated by three equal ONEs or ZEROs at either the most significant or least significant bit positions of the 12-bit words. The combination of these two circuits detects 18 per cent of random single-bit errors and 31 per cent of two-bit errors. While this is insufficient to actually protect data integrity, it does provide a very simple and effective method for monitoring line/circuit error rate and general health of the system. It may be noted that additional logic circuits may be employed to check for violation of other code construction rules such as weight or intra run-length within the 12-bit words.

FIG. 4 is an alternative embodiment to the decoder of FIG. 3. It shows a ROM adapted to contain 4096.times.8 bits of data which provides full invalid detection of 12-bit codes. When an error is detected an error register is set to inform a controller of the incident. The remainder of the circuit is identical to that of FIG. 3.

FIG. 5 illustrates the elements of a transmission system necessary for the communication of the 12-bit linecode. It shows a plurality of input terminals 50 which could for example be the output terminals 22 of FIG. 2; these are connected to a conventional parallel/serial register 51 which is responsive to a load-pulse signal from a divide-by-twelve counter 52 driven from a clock source 53 to accept a 12-bit word from the input terminals 50 and convert it, under control of the clock signal, into channelized serial binary data. As mentioned above, the coding circuit, for example that of FIG. 2, periodically (e.g. at every frame, channel 0) inserts a SYNC word instead of an encoded binary word. The serial data is fed to a transmitter 54 for transmission on the link 55, to be received by a receive circuit 56 which includes a conventional clock recovery circuit. The serial binary words are fed to a serial/parallel converter circuit 57 which is responsive to the recovered clock signal for converting the serial data into parallel data which is momentarily stored into latch circuit 58 under control of a load pulse derived from the recovered clock by a divide-by-twelve circuit 59. A logic gate circuit 60 is responsive to the word representing the SYNC code appearing on the parallel outputs of circuit 57 for resetting the dividing circuit 59. This incidence appears on a terminal 61 for tranmission to a controller (not shown). The reset pulse indicates that the word presently being received is the data word for channel 0 and is therefore the beginning of a new frame of data. The counter 59 then continues to mark channel pulses until the next SYNC code word is detected. In a system adapted to the transmission of PCM information, the frame reports every 125 microseconds. For a 512 channel system, the channel rate is 4.096 MHz and the transmission code rate is 49.152 Mbs.

The method and circuits of the invention result in a very robust synchronization scheme. The derivation of the SYNC code word ensures that its bit pattern cannot be mimicked by any serial combination of valid data words and that it can only be mimicked by seriously distorted data. Also, since the SYNC code word is immediately recognizable by the circuitry, synchronization is instantly achieved. Upon loss of synchronization, its recovery takes place within less than 125 microseconds. In addition, the binary words encoded in accordance with the invention exhibit a statistically distributed DC balance and an edge density suitable for effective clock recovery at a receiving terminal. Furthermore, the encoding scheme permits the use of translation ROMs having a greatly reduced size from what would be expected through conventional design.