JP4356495B2 - Data processing apparatus and program - Google Patents

Description

  The present invention relates to an apparatus that processes data using HDLC (High-level Data Link Control Procedure), and more particularly to a data processing apparatus that speeds up flag detection processing.

HDLC is a data link layer standard defined by ISO (International Organization for Standardization) based on IBM's SDLC (Synchronous Data Link Control). Frame structure of HDLC, as shown in FIG. 2 5, and 8-bit flag indicating the start and end of the frame, the 8-bit address portion following the sequential flag, the control unit of 8 bits or 16 bits, any bit length It consists of an information part and a 16-bit FCS (Frame Check Sequence). Since the bit pattern of the flag is defined as 01111110, in the portion sandwiched between the flags indicating the start and end of the frame, if 5 bits 1 continue, the transmission side inserts bit 0 next (this Is called zero insertion), and the receiving side deletes the bit 0 (this is called zero deletion) to guarantee the uniqueness of the bit pattern of the flag. On the receiving side, the process of detecting the flag is repeated for each frame.

  Conventionally, there is a method disclosed in Patent Document 1 as such a flag detection method. The flag detection method disclosed in Patent Document 1 will be described below with reference to the flowcharts of FIGS. 26 and 27 and the diagrams showing the state changes of FIGS. In these figures, the input queue is data that will be subjected to the 0 deletion process, and the output queue is data that has been subjected to the 0 deletion process. FIG. 26 shows a start flag detection process, and FIG. 27 shows a process after the start flag is detected.

First, in order to flag detected before 0 deleted, selects the data of the head from one octet of the input queues (8 bits) (FIG. 28 (a), the 2 6 Step S31). Next, the flag detection table is searched, and (a) the number of bits to be deleted from the input queue (number of deleted bits) and (b) the data type (flag / normal data) are read (FIG. 28B, step S32). ). Here, the data type is not a flag, but the number of deleted bits = 1. Accordingly, “NO” is determined in step S33, and the first one bit is deleted from the input queue in step S35, and the process returns to step S31. Since no data is added to the output queue until the flag is detected, the leading 1 is deleted from the input queue as shown in FIG. 28C, but no data is added to the output queue.

  Again, 8 bits are selected from the input queue. This time, 01111110 is selected (FIG. 29A). By searching the flag detection table, it can be seen that the inputted 8 bits are flags and the number of deleted bits = 8. Therefore, “Yes” is determined in step S33, and the 8 bits of the flag are deleted from the input queue in step S34, and the start flag detection process is completed.

  Since the start flag is detected, the zero deletion process shown in FIG. 27 is executed next. Data of 1 octet (8 bits) is selected from the head of the input queue (FIG. 30 (a), step S41 in FIG. 27). Here, 01011011 is selected. Next, the 0 deletion table is searched, and (a) the number of bits to be added to the output queue (output bit number), (b) the number of bits to be deleted from the input queue (deletion bit number), and (c) the data type ( Normal data / flag / abort) is read (FIG. 30B, step S42). Here, as shown in FIG. 30B, the number of output bits = 5, the number of deleted bits = 5, and the data type = normal data. The reason why the last 3 bits 011 of the selected 8 bits are not added to the output queue is that this 011 is the same as the first 3 bits of the flag, so if 11110 follows that 3 bits, it becomes an end flag. Because. Accordingly, it is determined as step S43 “normal data”, 01011 is added to the output queue in step S44, and 01011 is deleted from the input queue in step S45, resulting in the state shown in FIG.

Thereafter, the processing of steps S41 to S45 is repeatedly executed from FIG. 31 to FIG. 39, the flag is detected in step S43 as shown in FIG. 40A, and the processing of one frame is completed. 33, 34, 35, 37, and 38, zero deletion is performed. When the processing for one frame is completed, the process returns to step S41 to process the next frame. If an abort is detected in step S43, the process returns to step S31 in FIG. 26 to perform flag detection processing.
Japanese translation of PCT publication No. 2002-520952

  However, in the conventional flag detection method, the flag detection is performed while deleting only the determined number of bits from the bit string selected from the input queue, so that the deletion process becomes complicated. In addition, the number of processes from the start of the input queue bit string to the start flag detection and the number of processes from the detection of a certain flag to the detection of the next flag increase or decrease. In particular, when there is data having the same bit arrangement as a part of the flag, and when a bit string that requires 0 deletion is continuous, the number of processing times increases and the processing time becomes long.

  The present invention has been made to solve such a problem, and the number of processes until the detection of the start flag and the number of processes from the detection of a certain flag to the detection of the next flag are not affected by the arrangement of the bit strings in the input queue. Thus, it aims at shortening processing time.

The invention according to claim 1 has a frame composed of a start flag, an end flag, and normal data sandwiched between them, and a zero insertion process is performed on the normal data in order to guarantee the uniqueness of the bit pattern of the flag. A data processing device for generating an output queue in which the flag and inserted 0 are deleted from an input queue of frame data, and means for selecting an input bit sequence from the input queue for each predetermined number of bits; Corresponding to each pattern of the input bit string, status data corresponding to the difference between the previous input bit string and the previous output bit string, the arrangement of the bit string of the predetermined number of bits, the type of data, and the output in which the inserted 0 is deleted use the bit string, and the combination is stored in advance a table of the next state data, the type of the current input bit string and data Te by searching the table, the type of data of the current input bit string, the input bit string corresponding data acquisition means for acquiring the output bit string and the next state data, the type of the acquired data, in this input bit string Flag detecting means for detecting a flag ; output bit string adding means for adding the acquired output bit string to the output queue; and input bit string deleting means for deleting the current input bit string from the input queue. Is a data processing device characterized by
The invention according to claim 2 has a frame composed of a start flag and an end flag, and normal data sandwiched between them, and a zero insertion process is performed on the normal data in order to guarantee the uniqueness of the bit pattern of the flag. A program for causing a computer of a data processing device that generates an output queue from which the flag and inserted 0 are deleted from an input queue of frame data to function as each unit of the data processing device according to claim 1. .

  According to the present invention, since a predetermined number of input bit strings selected from the input queue are processed regardless of their arrangement, the number of processes until the start flag is detected, and the process from detection of a certain flag to detection of the next flag is performed. The number of times is irrelevant to the arrangement of bit strings in the input queue, and the processing time is shortened.

Hereinafter, embodiments of the present invention will be described with reference to the drawings.
FIG. 1 is a block diagram showing the configuration of a transmission control circuit and a reception control circuit according to an embodiment of the present invention. The transmission control circuit 1 includes an FCS generation unit 11, a 0 insertion unit 12 connected to the output side, and a flag generation unit 13 connected to the output side. The reception control circuit 2 includes a 0 deletion / flag detection unit 21 and an error detection unit 22 connected to the output side thereof.

  The 0 insertion unit 12 includes an input queue storage unit 12b, a buffer memory 12c connected to the output side thereof, an output queue storage unit 12d connected to the output side thereof, a control unit 12a that controls each unit, and a control unit And a 0 insertion table 12e connected to 12a. The 0 deletion and flag detection unit 21 includes an input queue storage unit 21b, a buffer memory 21c connected to the output side thereof, an output queue storage unit 21d connected to the output side thereof, and a control unit that controls each unit. 21a and a 0 deletion and flag detection table 21e connected to the control unit 21a.

The HDLC frame data generated by a frame generation unit (not shown) is input to the FCS generation unit 11 of the transmission control circuit 1. The FCS generation unit 11 adds an FCS (error correction code) to the input HDLC frame data and outputs it to the 0 insertion unit 12. The 0 insertion unit 12 stores data in the input queue storage unit 12b under the control of the control unit 12a, reads the stored data into the buffer memory 12c in predetermined bit units, searches the 0 insertion table 12e, and searches for 0. Insertion processing is performed, and the data subjected to 0 insertion processing is sent from the buffer memory 12c to the output queue storage unit 12d. Further, control is performed so that the data stored in the output queue storage unit 12 d is sent to the flag generation unit 13. As will be described in detail later, the 0 insertion table 12e includes state data corresponding to the difference between the bit string read from the previous input queue storage unit 12b and the bit string sent to the previous output queue storage unit 12d, and a predetermined number of bits. Next state data corresponding to the difference between the bit string arrangement, the bit string sent to the output queue storage unit 12d and the number of bits, and the bit string read from the input queue storage unit 12b and the bit string sent to the output queue storage unit 12d All combinations are stored in advance. In addition, since a predetermined number of bit strings read from the input queue storage unit 12b are deleted from the input queue storage unit 12b regardless of the order of the bit strings, the number of times of 0 insertion processing is the number of bit strings read from the input queue storage unit 12b. It becomes unrelated to the line. Flag generating unit 1 3 adds a flag 01111110 to input data, and transmitted via the data transmission line (not shown) to the reception control circuit 2.

  The HDLC frame data transmitted from the transmission control circuit 1 is input to the 0 deletion and flag detection unit 21 of the reception control circuit 2 via a data transmission path (not shown). The 0 deletion and flag detection unit 21 stores data in the input queue storage unit 21b under the control of the control unit 21a, reads the stored data into the buffer memory 21c in units of predetermined bits, and performs the 0 deletion and flag detection table 21e. , The zero deletion and flag detection processing is performed, and the data subjected to the zero deletion and flag detection processing is sent from the buffer memory 21c to the output queue storage unit 21d. Further, control is performed so that the data stored in the output queue storage unit 21 d is sent to the error detection unit 22. As will be described in detail later, the zero deletion and flag detection table 21e includes state data corresponding to a difference between a bit string read from the previous input queue storage unit 12b and a bit string sent to the previous output queue storage unit 12d, predetermined data The next bit sequence corresponding to the arrangement of the bit sequence of the number of bits, the bit sequence sent to the output queue storage unit 21d and its bit number, the bit sequence read from the input queue storage unit 21b and the bit sequence sent to the output queue storage unit 21d All combinations of status data and data types (normal data / flag / abort) are stored in advance. Further, since a predetermined number of bit strings read from the input queue storage unit 21b are deleted from the input queue storage unit 21b regardless of their arrangement, the number of times of 0 deletion processing is the number of bit strings read from the input queue storage unit 21b. Is irrelevant. The error detection unit 22 performs error correction processing using the FCS of the input data and sends it to a frame reception unit (not shown).

Hereinafter, the operation of the 0 insertion unit 12 of the transmission control circuit 1 will be described with reference to FIGS.
First, the contents of the 0 insertion table 12e will be described. In this embodiment, when data is read into the buffer memory 12c 8 bits at a time from the input queue storage unit 12b and 0 insertion is necessary, that is, when 5 1s continue, 0 insertion processing is performed, and the output queue storage unit To 12d. When, for example, 11101111 is read from the input queue storage unit 12b, 1110 is sent to the output queue storage unit 12d, and 1111 is not sent. In this embodiment, the remaining bits consisting of 1111 are stored as a state number, and are handled at the same time as the 8 bits read from the input queue storage unit 12b next time.

  Since there are four types of remaining bits, 1, 11, 111, and 1111, the types of remaining bits are determined by state numbers 0 to 4 as shown in FIG. The 0 insertion table 12e stores in advance all the combinations of the 8-bit bit string read from the input queue, the bit string output to the output queue storage unit 12d, the number of bits, and the state number.

Next, a procedure for creating the 0 insertion table 12e will be described.
[1] In the case of a table whose status number is 0: Created by the following procedures (1) to (4).
(1) For the 8 bits of interest, the bits are examined in order to determine whether 0 insertion is necessary.

<Law of judgment>
-Whether or not 0 insertion is necessary is confirmed by checking whether 5 consecutive 1s or 0 appears midway.
-If the number of consecutive 1s is less than 5, the extracted bits can be used as they are.
When the number of consecutive 1s reaches 5, the bit string determined so far by inserting 0s is taken as a sequence of extracted bits, and the number of consecutive 1s is counted again from 0.

(2) Perform the process in (1) and check all 8 bits. At the end of 8 bits, the following three states are possible.
(A) State in which the 8th bit ends with 0 (the number of consecutive 1s is 0)
(A) State immediately after the insertion of 0 at the 8th bit when the number of consecutive 1s is 5 (the number of consecutive 1s is 0)
(C) In the 8th bit, the number of consecutive 1s is 1 or more and less than 5 and affects the next extracted bit

(3) In the cases of (a) and (b), the bit string and the number of bits that have been created are used as a table. Since all the bits have been determined, the remaining bits are 0. This also means that the next state is 0 because the remaining number of bits is 0.

(4) In the case of (c), the determined bit string and the number of bits of the bit string are used as a table. The number of consecutive 1s at the end time is set as the next state number.
If there are no remaining bits → Next state: 0
If the remaining bit is 1 → Next state number: 1
In case of remaining bit 11 → next state number: 2
In case of remaining bit 111 → next state number: 3
In case of remaining bit 1111 → next state number: 4

[2] In the case of a table whose status number is other than 0 Created by the following procedures (1) to (5).
(1) Depending on the state number, the following bits are added before the target 8 bits.
Status number: 1 → 1 + (target 8 bits)
Status number: 2 → 11 + (target 8 bits)
Status number: 3 → 111 + (target 8 bits)
Status number: 4 → 1111 + (target 8 bits)

(2) For the bit string created in (1), the bits are examined in order to determine whether 0 insertion is necessary.
<Law of judgment>
-Whether or not 0 insertion is necessary is confirmed by checking whether 5 consecutive 1s or 0 appears midway.
-If the number of consecutive 1s is less than 5, the extracted bits can be used as they are.
When the number of consecutive 1s reaches 5, the bit string determined so far by inserting 0s is taken as a sequence of extracted bits, and the number of consecutive 1s is counted again from 0.

(3) The processing of (2) is performed and all the bits created in (1) are examined. At the end of all bits, the following three states are possible.
(A) The state in which the last bit ends with 0 (the number of consecutive 1s is 0)
(A) State immediately after the number of consecutive 1s is 5 in the last bit and 0 is inserted (the number of consecutive 1s is 0)
(C) A state in which the number of consecutive 1s is 1 or more and less than 5 in the last bit and affects the next extracted bit

(4) In the cases of (a) and (b), the bit string and the number of bits already created are tables. Since all the bits have been determined, the remaining bits are 0. This also means that the next state is 0 because the remaining number of bits is 0.

(5) In the case of (c), the determined bit string and the number of bits of the bit string are used as a table. Further, the consecutive number of 1 at the end time is set as the next state number.
If there are no remaining bits → Next state number: 0
If the remaining bit is 1 → Next state number: 1
In case of remaining bit 11 → next state number: 2
In case of remaining bit 111 → next state number: 3
In case of remaining bit 1111 → next state number: 4

[3] Example of creation of 0 insertion table (when creating a conversion table of status number: 2 and input bit string: 10111101)
(1) Since it is in state 2, the previous bit string is a state ended at 11, and 1011101 is added to this and the determination bit string can be considered as 1110111101.
(2) For the bit string created in (1), if the extracted bit is created while considering the need for 0 insertion, it can be divided into 1111011110 + 1.
(3) Therefore, 111011110 and the number of bits “9” are obtained as extracted bits. Since the remaining “1” affects the next state, data cannot be determined this time, and the next state is set to 1.
(4) From the above, as a conversion table of state number: 2 and input bit string: 10111101,
Next state number: 1, number of output bits: 9, output bit string = 111011110
Is obtained.

  FIG. 3 shows a part of the 0 insertion table 12e. As shown in this figure, when the state number and the input bit string are determined, the next state number, the number of output bits, and the output bit string are determined correspondingly. Note that the state number of the bit string read first from the input queue storage unit 12b is 0.

  Next, the zero insertion method will be described with reference to the flowchart of FIG. 4 and the diagrams showing the state changes of FIGS. In these figures, the input queue is a bit string stored in the input queue storage unit 12b, and the output queue is a bit string stored in the output queue storage unit 12d. Note that the bit sequence of the input queue is the same as the bit sequence of the input queue in the conventional example.

First, data of 1 octet (8 bits) is selected from the head of the 6 octet (48 bits) input queue (FIG. 5A, step S1 in FIG. 4). In FIG. 5A, 01011011 surrounded by a frame indicates the selected 8 bits. Next, the 0 insertion table is searched and (a) the next state number (next state number), (b) the number of bits to be added to the output queue (number of output bits), (c) and the number to be added to the output queue. A bit string (output bit string) is read (FIG. 5B, step S2). In the 0 insertion table, the above data (a), (b) and (c) are stored in advance for the product (2 ⁸ × 5 = 1,280) of all 8-bit combinations and the number of state numbers inputted. ing.

  Here, the next state number = 2, the number of output bits = 6, and the output bit string = 010110. The state (initial state) of 01011011 selected from the input queue is 0. Here, the reason why not all of the selected 8 bits are added to the output queue is that the last 2 bits 11 of the selected 8 bits are set to 0 if the 2 bits are followed by 3 1s. This is because an insertion process is performed, and it is necessary to process together with the first three bits to be selected next, which is undecided. Therefore, here, 010110 is added to the output queue (step S3). On the other hand, 01011011 is deleted from the input queue and the next state number is stored (step S4). FIG. 5C shows an input queue from which 011011011 has been deleted and an output queue to which 0110110 has been added. Here, the double line assigned to 010110 of the input queue represents the deleted bit string, and the halftone represents the bit string deleted this time. The underline added to the output queue represents the bit string added this time.

  The above steps S1 to S4 are repeated until there is no bit string in the input queue (step S5). Here, 10111101 is selected as shown in FIG. The state number of this input bit string is 2 stored last time. When the 0 insertion table 12e is searched using this input bit string and state number, as shown in FIG. 6B, the next state number = 1, the number of output bits = 9, and the output bit string = 111011110. Here, the first 2 bits 11 of the output bit string are not output bits of what was previously selected and deleted from the input queue, but are stored by the next state number. Next, 1110111110 is added to the output queue (step S3), 10111101 is deleted from the input queue, and the next state number (= 1) is saved (step S4), resulting in the state shown in FIG. 6C. .

  Thereafter, the processes of steps S1 to S4 are repeatedly executed from FIG. 7 to FIG. 10, and when the state shown in FIG. 11 is reached, “Yes” is determined in step S5. Therefore, the state number is determined in the next step S6. One number corresponding to the state number is added to the output queue, and the processing of one frame is completed. In FIGS. 7, 8, 9 and 10, zero insertion is performed.

  As described above, in the 0 insertion processing of this embodiment, since 1 octet (8 bits) selected from the input queue is deleted regardless of the arrangement of the input bit string, the processing is simple and the number of octets in the input queue. It is completed by the same number of loop processes.

  Next, the operation of the zero deletion and flag detection unit 21 of the transmission / reception control circuit 2 will be described with reference to FIGS.

  First, the contents of the 0 deletion and flag detection table 21e will be described. In this embodiment, when data is read into the buffer memory 21c 8 bits at a time from the input queue storage unit 21b and 0 deletion is necessary, that is, when 5 1s continue, 0 deletion processing is performed, and the output queue storage unit Added to 21d. Further, when the flag 01111110 is read, a flag detection process is performed. Here, when the start flag, which is the first flag of the frame, is detected, the zero deletion process is started for data read thereafter, and when the end flag, which is the last flag of the frame, is detected, The 0 deletion process for one frame is completed. Similarly to the 0 insertion process, the state number is stored to identify the remaining bit strings not added to the output queue among the bit strings selected from the input queue.

  There are 13 state numbers from state 0 to state 12, as shown in FIG. The 0 deletion and flag detection table 21e includes an 8-bit bit string read from the input queue 21b, a bit string output to the output queue storage unit 21d, the number of bits, and a data type (normal data / flag / abort). ) And all combinations of state numbers are stored in advance.

Next, a procedure for creating the 0 deletion and flag detection table 21e will be described.
[1] In the case of a table in state 0 Created by the following procedures (1) to (5).

(1) For the 8 bits of interest, the bits are examined in order to determine whether a flag is present and whether 0 deletion is necessary.
<Law of judgment>
-Whether or not 0 insertion is necessary is confirmed by checking whether 5 consecutive 1s or 0 appears midway.
However, in order to consider the presence of the flag, it is necessary to distinguish between the case of 1 starting from 1 and the case of 1 starting from 0.
In the case of 1 continuation starting from 1, if the number of continuations of 1 is less than 5, the extracted bit sequence is used as it is.
If the number of consecutive 1s starts with 1 and the number of consecutive 1s is 5 and the next bit is 0, the one with the 0 removed is taken as a sequence of extracted bits.
-If the number of consecutive 1s starts from 1, and the number of consecutive 1s is 6, it is invalid data, so the type is “invalid (aborted)”.
In the case of 1 consecutive starting from 0, if the number of consecutive 1s is less than 5, the extracted bits are used as they are.
-In the case of a sequence of 1 starting from 0, if the number of consecutive 1s is 5 and the next bit is 0, the one with the 0 deleted is taken as a sequence of bits.
-In the case of 1 consecutive starting from 0, if the number of consecutive 1s is 6 and the next bit is 0, the bit sequence represents a flag.
The type is “flag”. At this time, the sequence of 01111110 corresponding to the flag is not included in the extracted bits.
In the case of 1 continuous starting from 0, if the number of 1 continuous is 7, it is invalid data, so the type is “invalid”.

(2) Perform the process of (1) and check all 8 bits. At the end of 8 bits, the following four states can be considered.
(A) When the 8th bit ends with 0 (b) When 1 ends up to the 7th bit and 1 ends, and the 8th bit deletes 0 (c) When the 8th bit ends with 1 When it is 1 or more and less than 6, and the processing depends on the next fetch bit (D) When the data type is "abnormal"

(3) In the cases of (a) and (b), the data type is “normal”, and the generated bit string and the number of bits of the bit string are used as a table. Also, since all bits have been determined, the remaining bits are 0. This means that the next state is 0 because the remaining number of bits is 0.

(4) In the case of (c), the data type is “normal”, the created bit string and the number of bits are in a table. Further, the next state number is determined according to the state of the bit which is not fixed at the end time.
If the remaining bits are 0 → Next state number: 1
If the remaining bit is 1, then next state number: 2
If the remaining bits are 01 → Next state number: 3
When the remaining bit is 11, the next state number: 4
If the remaining bits are 011 → next state number: 5
If the remaining bits are 111 → next state number: 6
If the remaining bits are 0111 → next state number: 7
If the remaining bits are 1111 → next state number: 8
If the remaining bits are 01111 → next state number: 9
If the remaining bits are 11111 → next state number: 10
If the remaining bits are 011111 → next state number: 11
If the remaining bits are 0111111 → next state number: 12
(5) In the case of (d), the data type is “abnormal”.

[2] In the case of a table whose status number is other than 0 Created by the following procedures (1) to (6).
(1) Depending on the state, the following bits are added before the target 8 bits.
Status number: 1 → 0 + (target 8 bits)
Status number: 2 → 1 + (target 8 bits)
Status number: 3 → 01 + (target 8 bits)
Status number: 4 → 11 + (target 8 bits)
Status number: 5 → 011 + (target 8 bits)
Status number: 6 → 111 + (target 8 bits)
Status number: 7 → 0111 + (target 8 bits)
Status number: 8 → 1111 + (target 8 bits)
Status number: 9 → 01111 + (target 8 bits)
Status number: 10 → 11111 + (target 8 bits)
Status number: 11 → 011111 + (target 8 bits)
Status number: 12 → 0111111 + (target 8 bits)

(2) For the bit string created in (1), the bits are examined in order to determine whether a flag is present and whether 0 deletion is necessary.
<Law of judgment>
-Whether or not 0 insertion is necessary is confirmed by checking whether 5 consecutive 1s or 0 appears midway.
However, in order to consider the presence of the flag, it is necessary to distinguish between a series of 1 starting from 1 and a series of 1 starting from 0.
In the case of 1 continuation starting from 1, if the number of continuations of 1 is less than 5, the extracted bit sequence is used as it is.
In the case of 1 consecutive starting from 1, if the number of consecutive 1s is 5 and the next bit is 0, the one with the 0 deleted is taken as a sequence of bits.
In the case of 1 continuous starting from 1, if the number of continuous 1 is 6, it is invalid data, so the type is “invalid”.
In the case of 1 consecutive starting from 0, if the number of consecutive 1s is less than 5, the extracted bits are used as they are.
-In the case of a sequence of 1 starting from 0, if the number of consecutive 1s is 5 and the next bit is 0, the one with the 0 deleted is taken as a sequence of bits.
-In the case of 1 consecutive starting from 0, if the number of consecutive 1s is 6 and the next bit is 0, the bit sequence represents a flag.
The type is “flag”. At this time, the sequence of 01111110 corresponding to the flag is not included in the extracted bits.
In the case of 1 continuous starting from 0, if the number of 1 continuous is 7, it is invalid data, so the type is “invalid”.

(3) The processing of (2) is performed and all the bits created in (1) are examined. At the end of all bits, the following four states are possible.
(A) When the 8th bit ends with 0 (b) When 1 ends with 5 consecutive bits up to the 7th bit, and when the 8th bit deletes 0 (c) When the 8th bit ends with 1 When it is 1 or more and less than 6 and processing depends on the next fetch bit (d) When the data type is "abnormal"

(4) In the cases of (a) and (b), the data type is “normal”, and the generated bit string and the number of bits of the bit string are used as a table. Since all the bits have been determined, the remaining bits are 0. This means that the next state is 0 because the remaining number of bits is 0.

(5) In the case of (c), the data type is “normal”, the created bit string and the number of bits are in a table. Further, the next state number is determined according to the state of the bit which is not fixed at the end time.
If the remaining bits are 0 → Next state number: 1
If the remaining bit is 1, then next state number: 2
If the remaining bits are 01 → Next state number: 3
When the remaining bit is 11, the next state number: 4
If the remaining bits are 011 → next state number: 5
If the remaining bits are 111 → next state number: 6
If the remaining bits are 0111 → next state number: 7
If the remaining bits are 1111 → next state number: 8
If the remaining bits are 01111 → next state number: 9
If the remaining bits are 11111 → next state number: 10
If the remaining bits are 011111 → next state number: 11
If the remaining bits are 0111111 → next state number: 12
(6) In the case of (d), the data type is “abnormal”.

[3] Example of creating a 0 deletion table (in the case of creating a conversion table of state number: 12, input bit string: 00101101)
(1) Since the state number is 12, the previous bit string ends in 0111111. With this addition of 00101101 to this, the determination bit string can be considered as 011111100101101.
(2) With regard to the bit string created in (1), when taking out bits are created while considering the presence of the flag and the need for 0 deletion, it can be divided into 01111110 + 01011 + 01. Therefore, from the first 01111110, the type is a flag, the extraction bit is 01011, and the number of bits is 5.
Since the remaining 01 affects the next state, data cannot be determined this time, and the next state number is set to 3.
From the above, as a conversion table of state number: 12, input bit string: 00101101,
Next state number: 3, number of output bits: 5, output bit string = 111111110
Is obtained.

  FIG. 13 shows a part of the 0 deletion and flag detection table 21e. As shown in this figure, when the state number and the input bit string are determined, the data type is determined correspondingly, and the next state number, the number of output bits, and the output bit string are determined. Note that the state number of the bit string read first from the input queue storage unit 12b is 0.

  Next, the zero deletion and flag detection method will be described using the flowcharts of FIGS. 14 and 15 and the diagrams showing the state changes of FIGS. In these figures, an input queue is data that will be subjected to 0 deletion and flag detection processing, and an output queue is data that has been subjected to 0 deletion and flag detection processing. FIG. 14 shows the start flag detection process, and FIG. 15 shows the process after the start flag is detected. Note that the bit sequence of the input queue is the same as the bit sequence of the input queue in the conventional example.

  First, in order to detect a flag before deleting 0, data of 1 octet (8 bits) is selected from the head of the input queue (FIG. 16A, step S11 in FIG. 14). In FIG. 16A, 10111111 surrounded by a frame indicates 8 bits selected. Next, the 0 deletion and flag detection table 21e is searched and (a) the next state number, (b) the data type (normal data / flag / abort), and (c) the number of bits added to the output queue (number of output bits). And (d) reading out a bit string (output bit string) to be added to the output queue. (FIG. 16B, step S12). Here, the next state number = 12, the data type = normal, the number of output bits = 1, and the output bit string = 1. Therefore, since it is not a flag, it is determined as “No” in Step S13, and 8 bits are deleted from the input queue in Step S14 and the state number 12 is stored, and then the process returns to Step S11. Since no data is added to the output queue until the flag is detected, as shown in FIG. 16C, 10111111 is deleted from the input queue and no data is added to the output queue.

  Again, 8 bits are selected from the input queue (step S11). This time, 00101101 is selected (FIG. 17A). The state number of this input bit string is 12 stored last time. When the 0 deletion and flag detection table 21e is searched using this input bit string and state number (step S12), next state number = 3, data type = flag, number of output bits = 5, and output bit string = 01011 (FIG. 17). (B)). Since the flag is detected, it is determined as “Yes” in Step S13, and after adding the output bit string to the output queue in Step S15, 00101101 is deleted and the state number 3 is stored in Step S16, and the start flag detection process Finish.

  Since the start flag is detected, the zero deletion process shown in FIG. 15 is executed next. Data of 1 octet (8 bits) is selected from the head of the input queue (FIG. 18A, step S21 in FIG. 15). Here, 11011110 is selected. Next, when the 0 deletion and flag detection table 21e is searched (step S22), the next state number = 1, the data type = normal, the number of output bits = 9, and the output bit string = 0111101111 (FIG. 18B). Accordingly, step S23 is determined to be normal data, and 011101111 is added to the output queue in step S24, and 11011110 is deleted from the input queue in step S25, and state number 1 is stored (FIG. 18C).

  Thereafter, the processing of steps S21 to S25 is repeatedly executed from FIG. 19 to FIG. 24, and the flag is detected at step S23 as shown in FIG. In FIG. 19, 20, 21, 22, and 24, 0 deletion is performed. When the processing for one frame is completed, the process returns to step S21 to process the next frame. If an abort is detected in step S23, the process returns to step S11 in FIG. 14 to perform flag detection processing.

  As described above, in the 0 deletion process of the present embodiment, all the 1 octets (8 bits) selected from the input queue are deleted regardless of the arrangement of the input bit strings, so that the process is simple and the number of octets in the input queue. It is completed by the same number of loop processes.

  In the above description, the bit string is read from the input queue in units of 8 bits of the optimal value, but may be read in units of bits other than 8 bits. Further, the present invention is not only the HDLC procedure but also a process for converting the sequence of bit strings according to a specific rule, and can be similarly applied to a process for increasing or decreasing the number of bits before and after the conversion.

FIG. 1 is a block diagram showing a configuration of a transmission circuit and a reception control circuit according to an embodiment of the present invention. It is a figure which shows the state number of 0 insertion table in embodiment of this invention. It is a figure which shows the excerpt of 0 insertion table in embodiment of this invention. It is a flowchart of 0 insertion processing in the embodiment of the present invention. It is a figure which shows the state change of 0 insertion process in embodiment of this invention. It is a figure which shows the state change of 0 insertion process in embodiment of this invention. It is a figure which shows the state change of 0 insertion process in embodiment of this invention. It is a figure which shows the state change of 0 insertion process in embodiment of this invention. It is a figure which shows the state change of 0 insertion process in embodiment of this invention. It is a figure which shows the state change of 0 insertion process in embodiment of this invention. It is a figure which shows the state change of 0 insertion process in embodiment of this invention. It is a figure which shows the state number of 0 deletion and flag detection table in embodiment of this invention. It is a figure which shows 0 deletion and the extract of a flag detection table in embodiment of this invention. It is a flowchart of the start flag detection process in the embodiment of the present invention. It is a flowchart of 0 deletion processing in the embodiment of the present invention. It is a figure which shows the state change of the start flag detection process in embodiment of this invention. It is a figure which shows the state change of the start flag detection process in embodiment of this invention. It is a figure which shows the state change of 0 deletion process in embodiment of this invention. It is a figure which shows the state change of 0 deletion process in embodiment of this invention. It is a figure which shows the state change of 0 deletion process in embodiment of this invention. It is a figure which shows the state change of 0 deletion process in embodiment of this invention. It is a figure which shows the state change of 0 deletion process in embodiment of this invention. It is a figure which shows the state change of 0 deletion process in embodiment of this invention. It is a figure which shows the state change of 0 deletion process in embodiment of this invention. It is a figure which shows the structure of a HDLC frame. It is a flowchart of the conventional start flag detection process. It is a flowchart of the conventional 0 deletion process. It is a figure which shows the state change of the conventional start flag detection process. It is a figure which shows the state change of the conventional start flag detection process. It is a figure which shows the state change of the conventional 0 deletion process. It is a figure which shows the state change of the conventional 0 deletion process. It is a figure which shows the state change of the conventional 0 deletion process. It is a figure which shows the state change of the conventional 0 deletion process. It is a figure which shows the state change of the conventional 0 deletion process. It is a figure which shows the state change of the conventional 0 deletion process. It is a figure which shows the state change of the conventional 0 deletion process. It is a figure which shows the state change of the conventional 0 deletion process. It is a figure which shows the state change of the conventional 0 deletion process. It is a figure which shows the state change of the conventional 0 deletion process. It is a figure which shows the state change of the conventional 0 deletion process.

Explanation of symbols

  12 ... 0 insertion circuit, 12a, 21a ... control unit, 12b, 21b ... input queue storage unit, 12d, 21d ... output queue storage unit, 12e ... 0 insertion table, 21 ... 0 deletion and flag detection unit, 21e... 0 deletion and flag detection table.

Claims (2)

The flag from the input queue of frame data having a frame composed of a start flag and an end flag, and normal data sandwiched between them, and in which 0 insertion processing is performed on the normal data to guarantee the uniqueness of the bit pattern of the flag And a data processing device for generating an output queue in which inserted zeros are deleted,
It means for the input bit string by selecting the bit sequence for every predetermined number of bits from the input queue,
Corresponding to each pattern of the input bit string, the status data corresponding to the difference between the previous input bit string and the previous output bit string, the arrangement of the bit string of the predetermined number of bits, the type of data, and the output in which the inserted 0 is deleted A table in which combinations of bit strings and next state data are stored in advance ;
Search the table using the current input bit string and data type, input bit string corresponding data acquisition means for acquiring the current input bit string data type, output bit string and next state data;
Flag detection means for detecting a flag in the current input bit string according to the type of the acquired data ,
Output bit string adding means for adding the acquired output bit string to the output queue;
Input bit string deletion means for deleting the current input bit string from the input queue;
A data processing apparatus comprising: The flag from an input queue of frame data having a frame composed of a start flag and an end flag, and normal data sandwiched between them, and in which normal data is subjected to 0 insertion processing in order to guarantee the uniqueness of the bit pattern of the flag A program for causing a computer of a data processing apparatus that generates an output queue from which inserted zeros are deleted to function as each unit of the data processing apparatus according to claim 1 .

Images