# Patent

## Title
Optimal TCM codec search method for dual stream systems, and encoder/decoder using the same

## Abstract

Provided is a method for searching for an optimal coder suitable to a dual stream transmission method of a DTV transceiving apparatus, and an encoder and a decoder employing the optimal coder searching method. The optimal coder searching method includes the steps of: a) determining a mixed pattern of normal stream and robust stream; b) determining a trellis structure of the robust stream which is applied to the mixed pattern based on how coders are connected; c) forming a dual stream trellis by mixing a trellis of the normal stream, which is a normal stream trellis, and a trellis of the robust stream, which is a robust stream trellis; d) computing a free distance at departing points of the dual stream trellis structure based on a dual stream free distance computation termination condition; and e) determining the optimal coder based on the free distance.

## Background
TECHNICAL FIELD
The present invention relates to a Digital Television (DTV) transceiving apparatus for transmitting/receiving dual stream, which is a part of a reception performance improvement project of the DTV standard A/53 of the Advanced Television System Committee (ATSC). More particularly, the present invention relates to a method for searching for an optimal codec suitable to a dual stream transmission method of a DTV transceiving apparatus, and an encoder and a decoder employing the optimal codec searching method.
BACKGROUND ART
The 8-Vestigial Side Band (VSB) method, which is a Digital Television (DTV) broadcasting standard adopted by the North America and Korea, hardly provides indoor and mobile reception performance desired by broadcasting companies.
To solve the problem, the Advanced Television System Committee (ATSC) has collected suggestions for improving the DTV reception performance and developed a DTV transceiving system using a dual stream structure. The present invention provides a trellis coding searching method which is used to generate robust stream in the DTV transceiving system using a dual stream structure. Conventional technologies and search algorithms search only for an optimal single stream codec. When the single stream codec search algorithm is used to search for an optimal dual stream codec, it cannot find out an optimal codec due to missing of a free distance computation termination condition that appears only in dual stream. The present invention provides the free distance termination condition to search for an optimal dual stream codec.
DISCLOSURE
Technical Problem
It is, therefore, an object of the present invention to provide a method for searching for an optimal codec suitable to a dual stream transmission method, and an encoder and a decoder employing the optimal codec searching method.
The other objects and advantages of the present invention can be understood in the following description and embodiments of the present invention. Also, it is apparent to those skilled in the art of the present invention that the objects and advantages of the present invention can be easily realized by the means as claimed and combinations thereof.
Technical Solution
In accordance with one aspect of the present invention, there is provided a method for searching for an optimal codec suitable for dual stream transmission, which includes the steps of: a) determining a mixed pattern of normal stream and robust stream; b) determining a trellis structure of the robust stream which is applied to the mixed pattern based on how codecs are connected; c) forming a dual stream trellis by mixing a trellis of the normal stream, which is a normal stream trellis, and a trellis of the robust stream, which is a robust stream trellis; d) computing a free distance at departing points of the dual stream trellis structure based on a dual stream free distance computation termination condition; and e) determining the optimal codec based on the free distance.
The mixed pattern includes a normal stream trellis or a robust stream trellis maintained as much as 4Z steps, Z being a natural number, and the dual stream trellis structure is formed to satisfy a condition that a normal stream state and a robust stream state are equal to modulo 4.
The dual stream free distance computation termination condition includes that a current step is positioned in the normal stream trellis, and that two paths reach predetermined states p and q to satisfy p=q modulo 4.
In accordance with another aspect of the present invention, there is provided an apparatus for decoding dual stream, which includes: a receiving means for converting receiving signals into baseband signals; an equalizing means for determining a symbol level of the receiving signals; and a decoding means for decoding the symbol level into data symbols. The data symbol and a subsequent state are determined in a codec determined by forming a dual stream trellis by mixing a normal stream trellis and a robust stream trellis and by referring to a dual stream free distance computation termination condition at departing points of the dual stream trellis structure.
Advantageous Effects
The present invention provides an optimal codec searching method by performing additional coding onto robust stream which are transmitted at a 1⁄2 transmission rate and creating 1⁄4 rate robust stream to thereby improve performance of conventional standard 8-Vestigial Side Band (VSB).



DESCRIPTION OF DRAWINGS
The above and other objects and features of the present invention will become apparent from the following description of the preferred embodiments given in conjunction with the accompanying drawings, in which:
FIG. 1 is a view illustrating how to form a trellis structure with dual stream including robust data and normal data;
FIG. 2 is a view describing a condition for terminating computation of a free distance between two paths in a dual stream trellis structure of FIG. 1;
FIG. 3 is a block diagram showing an example of a 1⁄4 rate coder designed by combining a 1⁄2 rate coder with a general 8-VSB coder;
FIG. 4 is a view showing an equivalent coder model of an coder shown in FIG. 3;
FIG. 5 is an exemplary view illustrating a trellis of an equivalent 1⁄6 rate coder;
FIG. 6 is an exemplary view describing a 1⁄4 rate coder designed by combining a 1⁄2 rate coder with a general 8-VSB coder;
FIG. 7 is a view showing an equivalent coder model of an coder shown in FIG. 6;
FIG. 8 is an exemplary view showing a trellis of an equivalent 2/6 rate coder; and
FIG. 9 is a flowchart describing an optimal codec searching method suitable to dual stream transmission in accordance with an embodiment of the present invention.



BEST MODE FOR THE INVENTION
Other objects and aspects of the invention will become apparent from the following description of the embodiments with reference to the accompanying drawings, which is set forth hereinafter. When specific description on a related art is considered to obscure the points of the present invention, the description will not be provided herein. Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings.
Generally, the minimum Euclidian distance between two paths that form an error event is defined as a free distance and a coder having the maximum free distance is defined as an optimal coder in a trellis coding system. A Digital Television (DTV) transceiving apparatus, however, uses a dual stream transmission method. The dual stream, which is also called mixed stream, includes normal stream, or normal data, and robust stream, or robust data. When a conventional optimal codec searching method is applied to the dual stream transmission, problems occur. Therefore, the present invention suggests a new optimal codec search algorithm suitable to the dual stream transmission. Hereinafter, a dual stream trellis structure and an optimal codec searching method based on the dual stream trellis structure will be described.
FIG. 1 is a view illustrating how to form a trellis structure with dual stream including robust data and normal data.
Referring to FIG. 1, a dual stream trellis structure is formed by duplicating trellis of normal data as many as a value obtained by dividing the number of robust stream states by the number of normal stream states, which is 2(V−2), and connecting the trellis of the normal stream with the trellis of the robust stream. Herein, V denotes the number of memories in a coder for coding the robust stream; m denotes the number of states of memories in a coder for coding the normal stream; and n denotes the number of states of memories in a coder for coding the robust stream. Generally, V is 4, and the number of states of the memories in the codec for coding the robust stream is 16 states. However, the present invention is not limited to them.
FIG. 2 is a view describing a condition for terminating computation of a free distance between two paths in the dual stream trellis structure of FIG. 1. A conventional free distance computation algorithm, which is developed by Saxena and Mulligan Wilson, has a termination condition that the distance computation is terminated only when two paths are combined into one state. However, an error may be caused when the termination condition is applied to a dual stream trellis structure. The present invention suggests provides a new ‘dual stream free distance computation termination condition’ suitable to the dual stream trellis structure.
To describe the ‘dual stream free distance computation termination condition’ with reference to FIG. 2, it is considered that the two paths are combined with each other and the distance computation is terminated, only when:
1) a current step t is disposed in a normal stream trellis;
2) two paths reach in the states of p and q, respectively, in the t step; and
3) p=q modulo 4.
In other words, when two paths departing from a point A in FIG. 2 pass through a robust stream trellis and arrive in a normal stream trellis. When the two paths reach states p and q on a step t to achieve a relation ship that p(4)=q(12)modulo 4, the distance computation is terminated and a free distance from the moment is computed.
In FIG. 2, the robust stream trellis is determined based on the coding rate of the robust stream encoder or how the robust stream trellis is connected to the normal stream encoder. Hereinafter, a method for generating a robust stream trellis will be described with reference to the structural outline of a dual stream coder.
FIG. 3 is a block diagram showing an example of a 1⁄4 rate coder designed by combining a 1⁄2 rate coder with a general 8-VSB coder.
Referring to FIG. 3, the dual stream coder is composed of a robust stream coder 310 and an 8-VSB coder 320. In the dual stream codec, signals are repeatedly inputted to the robust stream coder 310 having a 1⁄2 coding rate through a repeater 330 to be coded in the robust stream coder 310 at a 1⁄4 coding rate.
FIG. 4 is a view showing an equivalent coder model of an coder shown in FIG. 3, FIG. 5 is an exemplary view illustrating a trellis of an equivalent 1⁄6 rate coder. Since a 1⁄2 rate coder of the dual stream coder of FIG. 3 has an arbitrary structure, it cannot determine a general trellis. Thus, as illustrated in FIG. 5, trellises of two 1⁄3 coders are overlapped to determine a trellis of an equivalent 1⁄6 rate coder. Referring to FIG. 5, an input ‘0’ at a point ‘A’ follows a 500 path, and an input ‘1’ follows a 501 path to thereby form a trellis of the equivalent 1⁄6 coder. The trellis becomes the robust stream trellis of FIGS. 1 and 2 to form a dual stream trellis.
FIG. 6 is an exemplary view describing a 1⁄4 rate coder designed by combining a 1⁄2 rate coder with a general 8-VSB coder. The 1⁄4 rate coder is designed by repeating the output of a 1⁄2 rate coder 610 through two repeaters 620 and inputting the output to an 8-VSB coder 630 to make a robust stream coder have a 1⁄4 coding rate.
FIG. 7 is a view showing an equivalent coder model of an encoder shown in FIG. 6, and FIG. 8 is an exemplary view showing a trellis of an equivalent 2/6 rate coder. Since the coder of FIG. 4 repeats the output of the 1⁄2 rate coder twice and inputs the output to the 8-VSB coder, its equivalent circuit is formed as shown in FIG. 7.
Referring to FIG. 8, an input ‘1’ departing a point ‘B’ follows a path 601, and a trellis of an equivalent 2/6 coder is formed as illustrated in FIG. 8. The trellis becomes the robust stream trellis of FIGS. 1 and 2 to thereby form a dual stream trellis.
The present invention provides an algorithm for searching for an optimal coder having the maximum free distance by computing free distances of coders in a dual stream transceiving system. Differently from conventional technologies, the present invention targets on processing dual stream, or mixed stream trellis.
FIG. 9 is a flowchart describing an optimal codec searching method suitable to dual stream transmission in accordance with an embodiment of the present invention.
Referring to FIG. 9, at step S910, a mixed pattern of normal stream and robust stream is determined. In the mixed pattern of normal stream and robust stream, the trellises of the normal stream and the robust stream are maintained as much as 4Z steps. Herein, Z is a natural number. In other words, when N is a trellis of normal stream and R is a trellis of robust stream, the mixed pattern is formed to be NRRRRNNN . . . , NNRRRRNNNNN . . . , .
Subsequently, at step S920, the structure of a robust stream trellis to be applied to the mixed pattern is determined based on connection between coders. As described with reference to FIGS. 5 and 8, the robust stream trellis is determined based on the coder structures of FIGS. 3 and 4.
When the robust stream trellis is determined, a dual stream trellis is formed as shown in FIGS. 1 and 2. Herein, the structures of the normal stream trellis and the robust stream trellis should be formed to always satisfy a condition that state m=state n (modulo) 4 [m: normal state, n=robust stream state] at a step S where the normal stream trellis is converted into a robust stream trellis or vice versa.
At step S940, a free distance is computed at the departing point of the dual stream trellis structure based on the dual stream free distance computation termination condition. At step S950, the free distance computation is repeated to determine an optimal coder.
The method of the present invention is realized as a program and stored in a computer-readable recording medium such as CD-ROM, RAM, ROM, floppy disks, hard disks, and magneto-optical disks. Since the process can be easily implemented by those skilled in the art of the present invention, description on it will not be provided herein.
While the present invention has been described with respect to certain preferred embodiments, it will be apparent to those skilled in the art that various changes and modifications may be made without departing from the scope of the invention as defined in the following claims.

## Claims

1. A method for searching for an optimal codec suitable for dual stream transmission, comprising the steps of:
a) determining a mixed pattern of normal stream and robust stream;
b) determining a trellis structure of the robust stream which is applied to the mixed pattern based on how coders are connected;
c) forming a dual stream trellis by mixing a trellis of the normal stream, which is a normal stream trellis, and a trellis of the robust stream, which is a robust stream trellis;
d) computing a free distance at departing points of the dual stream trellis structure based on a dual stream free distance computation termination condition; and
e) determining the optimal coder based on the free distance.

2. The method as recited in claim 1, wherein the mixed pattern includes a normal stream trellis or a robust stream trellis maintained as much as 4Z steps, Z being a natural number.

3. The method as recited in claim 1, wherein the dual stream trellis structure is formed to satisfy a condition that a normal stream state and a robust stream state are equal to modulo 4.

4. The method as recited in claim 1, wherein the dual stream free distance computation termination condition includes that a current step is positioned in the normal stream trellis, and that two paths reach predetermined states p and q to satisfy p=q modulo 4.

5. The method as recited in claim 1, wherein the optimal coder is a coder having a maximum free distance.

6. A method for searching for an optimal codec suitable for dual stream transmission, comprising the steps of:
a) determining a mixed pattern of normal stream and robust stream, a trellis of the normal stream or the robust stream being maintained as much as 4Z steps where Z is a natural number;
b) determining a robust stream trellis structure to be applied to the mixed pattern based on how coders are connected;
c) forming a dual stream trellis by mixing the normal stream trellis with the robust stream trellis to satisfy a condition that a normal stream state and a robust stream state are equal to modulo 4;
d) computing a free distance based on a dual stream free distance computation termination condition which includes that a current step is positioned in the normal stream trellis, and that two paths reach predetermined states p and q to satisfy p=q modulo 4;
e) determining an optimal coder based on the free distance.

7. An apparatus for coding dual stream, comprising:
a coder configured to form a dual stream trellis structure by mixing a normal stream trellis and a robust stream trellis, and referring to a free distance computed at departing points of the dual stream trellis structure based on a dual stream free distance computation termination condition.

8. The coding apparatus as recited in claim 7, wherein the dual stream trellis structure is formed to satisfy a condition that a normal stream state and a robust stream state are equal to modulo 4.

9. The coding apparatus as recited in claim 7, wherein the dual stream free distance computation termination condition includes that a current step is positioned in the normal stream trellis, and that two paths reach predetermined states p and q to satisfy p=q modulo 4.

10. An apparatus for decoding dual stream, comprising:
a receiving means for converting receiving signals into baseband signals;
an equalizing means for determining a symbol level of the receiving signals; and
a decoding means for decoding the symbol level into data symbols,
wherein a data symbol and a subsequent state are determined in a coder determined by forming a dual stream trellis by mixing a normal stream trellis and a robust stream trellis and by referring to a dual stream free distance computation termination condition at departing points of the dual stream trellis structure.

11. The decoding apparatus as recited in claim 10, wherein the dual stream trellis structure is formed to satisfy a condition that a normal stream state and a robust stream state are equal to modulo 4.

12. The decoding apparatus as recited in claim 10, wherein dual stream free distance computation termination condition includes that a current step is positioned in the normal stream trellis, and that two paths reach predetermined states p and q to satisfy p=q modulo 4.