aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorEli Zaretskii2015-05-30 14:00:06 +0300
committerEli Zaretskii2015-05-30 14:00:06 +0300
commit5e73eab8faaa6c5198d445d8625db53971300777 (patch)
tree01b5d149f387a23d0862d4e36650e618593887cf
parent71f1139cf97e805f8e610dc477f2b90f0d8d4bee (diff)
downloademacs-5e73eab8faaa6c5198d445d8625db53971300777.tar.gz
emacs-5e73eab8faaa6c5198d445d8625db53971300777.zip
Restore EOL format testing in etags
* test/etags/ETAGS.good_1, test/etags/ETAGS.good_2: * test/etags/ETAGS.good_3, test/etags/ETAGS.good_4: * test/etags/ETAGS.good_5, test/etags/CTAGS.good: Adjust to test-case changes below. * test/etags/html-src/algrthms.html: Convert back to DOS EOL format. * test/etags/cp-src/c.C (B): Add back stray CR character. * test/etags/c-src/dostorture.c: Add back. * test/etags/Makefile (CSRC): Add back c-src/dostorture.c.
Diffstat
-rw-r--r--test/etags/CTAGS.good11
-rw-r--r--test/etags/ETAGS.good_1111
-rw-r--r--test/etags/ETAGS.good_2125
-rw-r--r--test/etags/ETAGS.good_3127
-rw-r--r--test/etags/ETAGS.good_4111
-rw-r--r--test/etags/ETAGS.good_5141
-rw-r--r--test/etags/Makefile2
-rw-r--r--test/etags/c-src/dostorture.c107
-rw-r--r--test/etags/cp-src/c.C2
-rw-r--r--test/etags/html-src/algrthms.html1038
10 files changed, 979 insertions, 796 deletions
diff --git a/test/etags/CTAGS.good b/test/etags/CTAGS.good
index 2cfadb9ec6e..52c335a5d4c 100644
--- a/test/etags/CTAGS.good
+++ b/test/etags/CTAGS.good
@@ -3544,7 +3544,9 @@ not_bol c-src/emacs/src/regex.h 391
3544not_eol c-src/emacs/src/regex.h 394 3544not_eol c-src/emacs/src/regex.h 394
3545not_single_kboard_state c-src/emacs/src/keyboard.c /^not_single_kboard_state (KBOARD *kboard)$/ 3545not_single_kboard_state c-src/emacs/src/keyboard.c /^not_single_kboard_state (KBOARD *kboard)$/
3546notag2 c-src/torture.c 26 3546notag2 c-src/torture.c 26
3547notag2 c-src/dostorture.c 26
3547notag4 c-src/torture.c 45 3548notag4 c-src/torture.c 45
3549notag4 c-src/dostorture.c 45
3548notinname c-src/etags.c /^#define notinname(c) (_nin[CHAR (c)]) \/* c is not / 3550notinname c-src/etags.c /^#define notinname(c) (_nin[CHAR (c)]) \/* c is not /
3549npending c-src/emacs/src/keyboard.c 7244 3551npending c-src/emacs/src/keyboard.c 7244
3550ntool_bar_items c-src/emacs/src/keyboard.c 7974 3552ntool_bar_items c-src/emacs/src/keyboard.c 7974
@@ -3715,8 +3717,11 @@ post pyt-src/server.py /^ def post(self):$/
3715post pyt-src/server.py /^ def post(self):$/ 3717post pyt-src/server.py /^ def post(self):$/
3716pot_etags_version c-src/etags.c 81 3718pot_etags_version c-src/etags.c 81
3717pp1 c-src/torture.c /^int pp1($/ 3719pp1 c-src/torture.c /^int pp1($/
3720pp1 c-src/dostorture.c /^int pp1($/
3718pp2 c-src/torture.c /^pp2$/ 3721pp2 c-src/torture.c /^pp2$/
3722pp2 c-src/dostorture.c /^pp2$/
3719pp3 c-src/torture.c /^pp3(int bar)$/ 3723pp3 c-src/torture.c /^pp3(int bar)$/
3724pp3 c-src/dostorture.c /^pp3(int bar)$/
3720pp_bas_cat prol-src/natded.prolog /^pp_bas_cat(Cat):-$/ 3725pp_bas_cat prol-src/natded.prolog /^pp_bas_cat(Cat):-$/
3721pp_cat prol-src/natded.prolog /^pp_cat(Syn:Sem):-$/ 3726pp_cat prol-src/natded.prolog /^pp_cat(Syn:Sem):-$/
3722pp_exp prol-src/natded.prolog /^pp_exp('NIL'):-$/ 3727pp_exp prol-src/natded.prolog /^pp_exp('NIL'):-$/
@@ -4097,12 +4102,18 @@ tag-re-match-p el-src/emacs/lisp/progmodes/etags.el /^(defun tag-re-match-p (re)
4097tag-symbol-match-p el-src/emacs/lisp/progmodes/etags.el /^(defun tag-symbol-match-p (tag)$/ 4102tag-symbol-match-p el-src/emacs/lisp/progmodes/etags.el /^(defun tag-symbol-match-p (tag)$/
4098tag-word-match-p el-src/emacs/lisp/progmodes/etags.el /^(defun tag-word-match-p (tag)$/ 4103tag-word-match-p el-src/emacs/lisp/progmodes/etags.el /^(defun tag-word-match-p (tag)$/
4099tag1 c-src/torture.c /^(*tag1 (sig, handler)) ()$/ 4104tag1 c-src/torture.c /^(*tag1 (sig, handler)) ()$/
4105tag1 c-src/dostorture.c /^(*tag1 (sig, handler)) ()$/
4100tag1 c-src/h.h 110 4106tag1 c-src/h.h 110
4101tag2 c-src/torture.c /^(*tag2 (sig, handler)) ()$/ 4107tag2 c-src/torture.c /^(*tag2 (sig, handler)) ()$/
4108tag2 c-src/dostorture.c /^(*tag2 (sig, handler)) ()$/
4102tag3 c-src/torture.c /^(*tag3 (int sig, void (*handler) (int))) (int)$/ 4109tag3 c-src/torture.c /^(*tag3 (int sig, void (*handler) (int))) (int)$/
4110tag3 c-src/dostorture.c /^(*tag3 (int sig, void (*handler) (int))) (int)$/
4103tag4 c-src/torture.c /^(*tag4 (int sig, void (*handler) (int))) (int)$/ 4111tag4 c-src/torture.c /^(*tag4 (int sig, void (*handler) (int))) (int)$/
4112tag4 c-src/dostorture.c /^(*tag4 (int sig, void (*handler) (int))) (int)$/
4104tag5 c-src/torture.c /^tag5 (handler, arg)$/ 4113tag5 c-src/torture.c /^tag5 (handler, arg)$/
4114tag5 c-src/dostorture.c /^tag5 (handler, arg)$/
4105tag6 c-src/torture.c /^tag6 (void (*handler) (void *), void *arg)$/ 4115tag6 c-src/torture.c /^tag6 (void (*handler) (void *), void *arg)$/
4116tag6 c-src/dostorture.c /^tag6 (void (*handler) (void *), void *arg)$/
4106tag_or_ch c-src/emacs/src/lisp.h 3026 4117tag_or_ch c-src/emacs/src/lisp.h 3026
4107taggedfname c-src/etags.c 207 4118taggedfname c-src/etags.c 207
4108tags-add-tables el-src/emacs/lisp/progmodes/etags.el /^(defcustom tags-add-tables 'ask-user$/ 4119tags-add-tables el-src/emacs/lisp/progmodes/etags.el /^(defcustom tags-add-tables 'ask-user$/
diff --git a/test/etags/ETAGS.good_1 b/test/etags/ETAGS.good_1
index ebd079f253a..a8e826f5df3 100644
--- a/test/etags/ETAGS.good_1
+++ b/test/etags/ETAGS.good_1
@@ -579,6 +579,19 @@ char **tab_fill(tab_fill70,1129
579int tab_delete_first(91,1638 579int tab_delete_first(91,1638
580int tab_count_words(103,1820 580int tab_count_words(103,1820
581 581
582c-src/dostorture.c,198
583(*tag1 tag118,468
584#define notag2 26,577
585(*tag2 tag229,657
586(*tag3 tag339,809
587#define notag4 45,904
588(*tag4 tag448,1001
589tag5 57,1136
590tag6 66,1272
591int pp1(74,1389
592pp287,1504
593pp3(100,1616
594
582c-src/emacs/src/gmalloc.c,3539 595c-src/emacs/src/gmalloc.c,3539
583#define USE_PTHREAD25,1002 596#define USE_PTHREAD25,1002
584#undef get_current_dir_name33,1126 597#undef get_current_dir_name33,1126
@@ -1896,46 +1909,46 @@ template <class C, int n> class AT 52,1668
1896class AU 53,1716 1909class AU 53,1716
1897class B<B54,1735 1910class B<B54,1735
1898class B<int> { void f(54,1735 1911class B<int> { void f(54,1735
1899const A::B::T& abt 55,1765 1912const A::B::T& abt 55,1766
1900class A 56,1791 1913class A 56,1792
1901class A { class B 56,1791 1914class A { class B 56,1792
1902class A 57,1826 1915class A 57,1827
1903 A operator+(59,1860 1916 A operator+(59,1861
1904is_muldiv_operation(61,1887 1917is_muldiv_operation(61,1888
1905domain foo 68,1955 1918domain foo 68,1956
1906 void f(69,1968 1919 void f(69,1969
1907void A::A(A72,1989 1920void A::A(A72,1990
1908struct A 73,2004 1921struct A 73,2005
1909struct B 74,2022 1922struct B 74,2023
1910void B::B(B75,2041 1923void B::B(B75,2042
1911void BE_Node::BE_Node(BE_Node76,2056 1924void BE_Node::BE_Node(BE_Node76,2057
1912class BE_Node 77,2083 1925class BE_Node 77,2084
1913struct foo 79,2102 1926struct foo 79,2103
1914class test 86,2156 1927class test 86,2157
1915 int f(87,2169 1928 int f(87,2170
1916 int ff(89,2231 1929 int ff(89,2232
1917 int g(90,2254 1930 int g(90,2255
1918class AST_Root 92,2278 1931class AST_Root 92,2279
1919AST_ConcreteType::AST_ConcreteType(99,2393 1932AST_ConcreteType::AST_ConcreteType(99,2394
1920AST_Array::AST_Array(107,2532 1933AST_Array::AST_Array(107,2533
1921 void f(115,2733 1934 void f(115,2734
1922struct A 117,2753 1935struct A 117,2754
1923A::~A(~A120,2777 1936A::~A(~A120,2778
1924struct B 122,2789 1937struct B 122,2790
1925 ~B(123,2800 1938 ~B(123,2801
1926enum {dog,dog126,2817 1939enum {dog,dog126,2818
1927enum {dog, cat}cat126,2817 1940enum {dog, cat}cat126,2818
1928enum {dog, cat} animals;126,2817 1941enum {dog, cat} animals;126,2818
1929struct {int teats;} cow;127,2842 1942struct {int teats;} cow;127,2843
1930class Boo 129,2868 1943class Boo 129,2869
1931 enum {dog,dog130,2880 1944 enum {dog,dog130,2881
1932 enum {dog, cat}cat130,2880 1945 enum {dog, cat}cat130,2881
1933 foo(133,2954 1946 foo(133,2955
1934 Boo(137,2995 1947 Boo(137,2996
1935Boo::Boo(141,3070 1948Boo::Boo(141,3071
1936typedef int should_see_this_one_enclosed_in_extern_C;149,3155 1949typedef int should_see_this_one_enclosed_in_extern_C;149,3156
1937typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3228 1950typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3229
1938typedef int should_see_this_array_type[should_see_this_array_type156,3310 1951typedef int should_see_this_array_type[should_see_this_array_type156,3311
1939 1952
1940cp-src/burton.cpp,124 1953cp-src/burton.cpp,124
1941::dummy::dummy test::dummy1(dummy11,0 1954::dummy::dummy test::dummy1(dummy11,0
@@ -2278,15 +2291,15 @@ Comunicati e iniziative32,976
2278Ultime notizie dall'associazione63,2030 2291Ultime notizie dall'associazione63,2030
2279 2292
2280html-src/algrthms.html,467 2293html-src/algrthms.html,467
2281Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,271 2294Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,277
2282Descriptionalgorithms10,472 2295Descriptionalgorithms10,481
2283Generating the Datagenalgorithm48,1948 2296Generating the Datagenalgorithm48,1995
2284Convolutionallyconalgorithm55,2458 2297Convolutionallyconalgorithm55,2512
2285Nextstatetable262,11326 2298Nextstatetable262,11587
2286Outputoutputtable350,13566 2299Outputoutputtable350,13915
2287Mapping the Channel Symbolsmapping433,15781 2300Mapping the Channel Symbolsmapping433,16213
2288Adding Noise to theaddnoise439,16169 2301Adding Noise to theaddnoise439,16607
2289Quantizing the Receivedquantizing469,18632 2302Quantizing the Receivedquantizing469,19100
2290 2303
2291html-src/software.html,439 2304html-src/software.html,439
2292Francesco Potortì Software Page9,280 2305Francesco Potortì Software Page9,280
diff --git a/test/etags/ETAGS.good_2 b/test/etags/ETAGS.good_2
index 12554bd95f1..73336b7aaa0 100644
--- a/test/etags/ETAGS.good_2
+++ b/test/etags/ETAGS.good_2
@@ -646,6 +646,19 @@ char **tab_fill(tab_fill70,1129
646int tab_delete_first(91,1638 646int tab_delete_first(91,1638
647int tab_count_words(103,1820 647int tab_count_words(103,1820
648 648
649c-src/dostorture.c,198
650(*tag1 tag118,468
651#define notag2 26,577
652(*tag2 tag229,657
653(*tag3 tag339,809
654#define notag4 45,904
655(*tag4 tag448,1001
656tag5 57,1136
657tag6 66,1272
658int pp1(74,1389
659pp287,1504
660pp3(100,1616
661
649c-src/emacs/src/gmalloc.c,6643 662c-src/emacs/src/gmalloc.c,6643
650#define USE_PTHREAD25,1002 663#define USE_PTHREAD25,1002
651#undef get_current_dir_name33,1126 664#undef get_current_dir_name33,1126
@@ -2402,53 +2415,53 @@ template <class C, int n> class AT 52,1668
2402class AU 53,1716 2415class AU 53,1716
2403class B<B54,1735 2416class B<B54,1735
2404class B<int> { void f(54,1735 2417class B<int> { void f(54,1735
2405const A::B::T& abt 55,1765 2418const A::B::T& abt 55,1766
2406class A 56,1791 2419class A 56,1792
2407class A { class B 56,1791 2420class A { class B 56,1792
2408class A { class B { int f(56,1791 2421class A { class B { int f(56,1792
2409class A 57,1826 2422class A 57,1827
2410 int get_data(58,1836 2423 int get_data(58,1837
2411 A operator+(59,1860 2424 A operator+(59,1861
2412is_muldiv_operation(61,1887 2425is_muldiv_operation(61,1888
2413domain foo 68,1955 2426domain foo 68,1956
2414 void f(69,1968 2427 void f(69,1969
2415void A::A(A72,1989 2428void A::A(A72,1990
2416struct A 73,2004 2429struct A 73,2005
2417struct A { A(73,2004 2430struct A { A(73,2005
2418struct B 74,2022 2431struct B 74,2023
2419struct B { B(74,2022 2432struct B { B(74,2023
2420void B::B(B75,2041 2433void B::B(B75,2042
2421void BE_Node::BE_Node(BE_Node76,2056 2434void BE_Node::BE_Node(BE_Node76,2057
2422class BE_Node 77,2083 2435class BE_Node 77,2084
2423struct foo 79,2102 2436struct foo 79,2103
2424class test 86,2156 2437class test 86,2157
2425 int f(87,2169 2438 int f(87,2170
2426 int ff(89,2231 2439 int ff(89,2232
2427 int g(90,2254 2440 int g(90,2255
2428class AST_Root 92,2278 2441class AST_Root 92,2279
2429class AST_Root;96,2327 2442class AST_Root;96,2328
2430AST_ConcreteType::AST_ConcreteType(99,2393 2443AST_ConcreteType::AST_ConcreteType(99,2394
2431AST_Array::AST_Array(107,2532 2444AST_Array::AST_Array(107,2533
2432 void f(115,2733 2445 void f(115,2734
2433struct A 117,2753 2446struct A 117,2754
2434 ~A(118,2764 2447 ~A(118,2765
2435A::~A(~A120,2777 2448A::~A(~A120,2778
2436struct B 122,2789 2449struct B 122,2790
2437 ~B(123,2800 2450 ~B(123,2801
2438enum {dog,dog126,2817 2451enum {dog,dog126,2818
2439enum {dog, cat}cat126,2817 2452enum {dog, cat}cat126,2818
2440enum {dog, cat} animals;126,2817 2453enum {dog, cat} animals;126,2818
2441struct {int teats;} cow;127,2842 2454struct {int teats;} cow;127,2843
2442class Boo 129,2868 2455class Boo 129,2869
2443 enum {dog,dog130,2880 2456 enum {dog,dog130,2881
2444 enum {dog, cat}cat130,2880 2457 enum {dog, cat}cat130,2881
2445 foo(133,2954 2458 foo(133,2955
2446 Boo(137,2995 2459 Boo(137,2996
2447 Boo(138,3052 2460 Boo(138,3053
2448Boo::Boo(141,3070 2461Boo::Boo(141,3071
2449typedef int should_see_this_one_enclosed_in_extern_C;149,3155 2462typedef int should_see_this_one_enclosed_in_extern_C;149,3156
2450typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3228 2463typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3229
2451typedef int should_see_this_array_type[should_see_this_array_type156,3310 2464typedef int should_see_this_array_type[should_see_this_array_type156,3311
2452 2465
2453cp-src/burton.cpp,124 2466cp-src/burton.cpp,124
2454::dummy::dummy test::dummy1(dummy11,0 2467::dummy::dummy test::dummy1(dummy11,0
@@ -2845,15 +2858,15 @@ Comunicati e iniziative32,976
2845Ultime notizie dall'associazione63,2030 2858Ultime notizie dall'associazione63,2030
2846 2859
2847html-src/algrthms.html,467 2860html-src/algrthms.html,467
2848Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,271 2861Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,277
2849Descriptionalgorithms10,472 2862Descriptionalgorithms10,481
2850Generating the Datagenalgorithm48,1948 2863Generating the Datagenalgorithm48,1995
2851Convolutionallyconalgorithm55,2458 2864Convolutionallyconalgorithm55,2512
2852Nextstatetable262,11326 2865Nextstatetable262,11587
2853Outputoutputtable350,13566 2866Outputoutputtable350,13915
2854Mapping the Channel Symbolsmapping433,15781 2867Mapping the Channel Symbolsmapping433,16213
2855Adding Noise to theaddnoise439,16169 2868Adding Noise to theaddnoise439,16607
2856Quantizing the Receivedquantizing469,18632 2869Quantizing the Receivedquantizing469,19100
2857 2870
2858html-src/software.html,439 2871html-src/software.html,439
2859Francesco Potortì Software Page9,280 2872Francesco Potortì Software Page9,280
diff --git a/test/etags/ETAGS.good_3 b/test/etags/ETAGS.good_3
index 714903c205f..950ed4ff67e 100644
--- a/test/etags/ETAGS.good_3
+++ b/test/etags/ETAGS.good_3
@@ -648,6 +648,19 @@ char **tab_fill(tab_fill70,1129
648int tab_delete_first(91,1638 648int tab_delete_first(91,1638
649int tab_count_words(103,1820 649int tab_count_words(103,1820
650 650
651c-src/dostorture.c,198
652(*tag1 tag118,468
653#define notag2 26,577
654(*tag2 tag229,657
655(*tag3 tag339,809
656#define notag4 45,904
657(*tag4 tag448,1001
658tag5 57,1136
659tag6 66,1272
660int pp1(74,1389
661pp287,1504
662pp3(100,1616
663
651c-src/emacs/src/gmalloc.c,4207 664c-src/emacs/src/gmalloc.c,4207
652#define USE_PTHREAD25,1002 665#define USE_PTHREAD25,1002
653#undef get_current_dir_name33,1126 666#undef get_current_dir_name33,1126
@@ -2186,54 +2199,54 @@ class AU 53,1716
2186class AU { T x;53,1716 2199class AU { T x;53,1716
2187class B<B54,1735 2200class B<B54,1735
2188class B<int> { void f(54,1735 2201class B<int> { void f(54,1735
2189const A::B::T& abt 55,1765 2202const A::B::T& abt 55,1766
2190class A 56,1791 2203class A 56,1792
2191class A { class B 56,1791 2204class A { class B 56,1792
2192class A 57,1826 2205class A 57,1827
2193 A operator+(59,1860 2206 A operator+(59,1861
2194is_muldiv_operation(61,1887 2207is_muldiv_operation(61,1888
2195domain foo 68,1955 2208domain foo 68,1956
2196 void f(69,1968 2209 void f(69,1969
2197void A::A(A72,1989 2210void A::A(A72,1990
2198struct A 73,2004 2211struct A 73,2005
2199struct B 74,2022 2212struct B 74,2023
2200void B::B(B75,2041 2213void B::B(B75,2042
2201void BE_Node::BE_Node(BE_Node76,2056 2214void BE_Node::BE_Node(BE_Node76,2057
2202class BE_Node 77,2083 2215class BE_Node 77,2084
2203struct foo 79,2102 2216struct foo 79,2103
2204 int x;80,2115 2217 int x;80,2116
2205class test 86,2156 2218class test 86,2157
2206 int f(87,2169 2219 int f(87,2170
2207 int ff(89,2231 2220 int ff(89,2232
2208 int g(90,2254 2221 int g(90,2255
2209class AST_Root 92,2278 2222class AST_Root 92,2279
2210AST_ConcreteType::AST_ConcreteType(99,2393 2223AST_ConcreteType::AST_ConcreteType(99,2394
2211AST_Array::AST_Array(107,2532 2224AST_Array::AST_Array(107,2533
2212 void f(115,2733 2225 void f(115,2734
2213struct A 117,2753 2226struct A 117,2754
2214A::~A(~A120,2777 2227A::~A(~A120,2778
2215struct B 122,2789 2228struct B 122,2790
2216 ~B(123,2800 2229 ~B(123,2801
2217enum {dog,dog126,2817 2230enum {dog,dog126,2818
2218enum {dog, cat}cat126,2817 2231enum {dog, cat}cat126,2818
2219enum {dog, cat} animals;126,2817 2232enum {dog, cat} animals;126,2818
2220struct {int teats;127,2842 2233struct {int teats;127,2843
2221struct {int teats;} cow;127,2842 2234struct {int teats;} cow;127,2843
2222class Boo 129,2868 2235class Boo 129,2869
2223 enum {dog,dog130,2880 2236 enum {dog,dog130,2881
2224 enum {dog, cat}cat130,2880 2237 enum {dog, cat}cat130,2881
2225 enum {dog, cat} animals;130,2880 2238 enum {dog, cat} animals;130,2881
2226 struct {int treats;131,2909 2239 struct {int treats;131,2910
2227 struct {int treats;} cow;131,2909 2240 struct {int treats;} cow;131,2910
2228 int i,132,2939 2241 int i,132,2940
2229 int i,a,132,2939 2242 int i,a,132,2940
2230 int i,a,b;132,2939 2243 int i,a,b;132,2940
2231 foo(133,2954 2244 foo(133,2955
2232 Boo(137,2995 2245 Boo(137,2996
2233Boo::Boo(141,3070 2246Boo::Boo(141,3071
2234typedef int should_see_this_one_enclosed_in_extern_C;149,3155 2247typedef int should_see_this_one_enclosed_in_extern_C;149,3156
2235typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3228 2248typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3229
2236typedef int should_see_this_array_type[should_see_this_array_type156,3310 2249typedef int should_see_this_array_type[should_see_this_array_type156,3311
2237 2250
2238cp-src/burton.cpp,124 2251cp-src/burton.cpp,124
2239::dummy::dummy test::dummy1(dummy11,0 2252::dummy::dummy test::dummy1(dummy11,0
@@ -2595,15 +2608,15 @@ Comunicati e iniziative32,976
2595Ultime notizie dall'associazione63,2030 2608Ultime notizie dall'associazione63,2030
2596 2609
2597html-src/algrthms.html,467 2610html-src/algrthms.html,467
2598Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,271 2611Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,277
2599Descriptionalgorithms10,472 2612Descriptionalgorithms10,481
2600Generating the Datagenalgorithm48,1948 2613Generating the Datagenalgorithm48,1995
2601Convolutionallyconalgorithm55,2458 2614Convolutionallyconalgorithm55,2512
2602Nextstatetable262,11326 2615Nextstatetable262,11587
2603Outputoutputtable350,13566 2616Outputoutputtable350,13915
2604Mapping the Channel Symbolsmapping433,15781 2617Mapping the Channel Symbolsmapping433,16213
2605Adding Noise to theaddnoise439,16169 2618Adding Noise to theaddnoise439,16607
2606Quantizing the Receivedquantizing469,18632 2619Quantizing the Receivedquantizing469,19100
2607 2620
2608html-src/software.html,439 2621html-src/software.html,439
2609Francesco Potortì Software Page9,280 2622Francesco Potortì Software Page9,280
diff --git a/test/etags/ETAGS.good_4 b/test/etags/ETAGS.good_4
index 5dd8d551460..01b27618f2b 100644
--- a/test/etags/ETAGS.good_4
+++ b/test/etags/ETAGS.good_4
@@ -603,6 +603,19 @@ char **tab_fill(tab_fill70,1129
603int tab_delete_first(91,1638 603int tab_delete_first(91,1638
604int tab_count_words(103,1820 604int tab_count_words(103,1820
605 605
606c-src/dostorture.c,198
607(*tag1 tag118,468
608#define notag2 26,577
609(*tag2 tag229,657
610(*tag3 tag339,809
611#define notag4 45,904
612(*tag4 tag448,1001
613tag5 57,1136
614tag6 66,1272
615int pp1(74,1389
616pp287,1504
617pp3(100,1616
618
606c-src/emacs/src/gmalloc.c,3539 619c-src/emacs/src/gmalloc.c,3539
607#define USE_PTHREAD25,1002 620#define USE_PTHREAD25,1002
608#undef get_current_dir_name33,1126 621#undef get_current_dir_name33,1126
@@ -2060,46 +2073,46 @@ template <class C, int n> class AT 52,1668
2060class AU 53,1716 2073class AU 53,1716
2061class B<B54,1735 2074class B<B54,1735
2062class B<int> { void f(54,1735 2075class B<int> { void f(54,1735
2063const A::B::T& abt 55,1765 2076const A::B::T& abt 55,1766
2064class A 56,1791 2077class A 56,1792
2065class A { class B 56,1791 2078class A { class B 56,1792
2066class A 57,1826 2079class A 57,1827
2067 A operator+(59,1860 2080 A operator+(59,1861
2068is_muldiv_operation(61,1887 2081is_muldiv_operation(61,1888
2069domain foo 68,1955 2082domain foo 68,1956
2070 void f(69,1968 2083 void f(69,1969
2071void A::A(A72,1989 2084void A::A(A72,1990
2072struct A 73,2004 2085struct A 73,2005
2073struct B 74,2022 2086struct B 74,2023
2074void B::B(B75,2041 2087void B::B(B75,2042
2075void BE_Node::BE_Node(BE_Node76,2056 2088void BE_Node::BE_Node(BE_Node76,2057
2076class BE_Node 77,2083 2089class BE_Node 77,2084
2077struct foo 79,2102 2090struct foo 79,2103
2078class test 86,2156 2091class test 86,2157
2079 int f(87,2169 2092 int f(87,2170
2080 int ff(89,2231 2093 int ff(89,2232
2081 int g(90,2254 2094 int g(90,2255
2082class AST_Root 92,2278 2095class AST_Root 92,2279
2083AST_ConcreteType::AST_ConcreteType(99,2393 2096AST_ConcreteType::AST_ConcreteType(99,2394
2084AST_Array::AST_Array(107,2532 2097AST_Array::AST_Array(107,2533
2085 void f(115,2733 2098 void f(115,2734
2086struct A 117,2753 2099struct A 117,2754
2087A::~A(~A120,2777 2100A::~A(~A120,2778
2088struct B 122,2789 2101struct B 122,2790
2089 ~B(123,2800 2102 ~B(123,2801
2090enum {dog,dog126,2817 2103enum {dog,dog126,2818
2091enum {dog, cat}cat126,2817 2104enum {dog, cat}cat126,2818
2092enum {dog, cat} animals;126,2817 2105enum {dog, cat} animals;126,2818
2093struct {int teats;} cow;127,2842 2106struct {int teats;} cow;127,2843
2094class Boo 129,2868 2107class Boo 129,2869
2095 enum {dog,dog130,2880 2108 enum {dog,dog130,2881
2096 enum {dog, cat}cat130,2880 2109 enum {dog, cat}cat130,2881
2097 foo(133,2954 2110 foo(133,2955
2098 Boo(137,2995 2111 Boo(137,2996
2099Boo::Boo(141,3070 2112Boo::Boo(141,3071
2100typedef int should_see_this_one_enclosed_in_extern_C;149,3155 2113typedef int should_see_this_one_enclosed_in_extern_C;149,3156
2101typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3228 2114typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3229
2102typedef int should_see_this_array_type[should_see_this_array_type156,3310 2115typedef int should_see_this_array_type[should_see_this_array_type156,3311
2103 2116
2104cp-src/burton.cpp,124 2117cp-src/burton.cpp,124
2105::dummy::dummy test::dummy1(dummy11,0 2118::dummy::dummy test::dummy1(dummy11,0
@@ -2442,15 +2455,15 @@ Comunicati e iniziative32,976
2442Ultime notizie dall'associazione63,2030 2455Ultime notizie dall'associazione63,2030
2443 2456
2444html-src/algrthms.html,467 2457html-src/algrthms.html,467
2445Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,271 2458Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,277
2446Descriptionalgorithms10,472 2459Descriptionalgorithms10,481
2447Generating the Datagenalgorithm48,1948 2460Generating the Datagenalgorithm48,1995
2448Convolutionallyconalgorithm55,2458 2461Convolutionallyconalgorithm55,2512
2449Nextstatetable262,11326 2462Nextstatetable262,11587
2450Outputoutputtable350,13566 2463Outputoutputtable350,13915
2451Mapping the Channel Symbolsmapping433,15781 2464Mapping the Channel Symbolsmapping433,16213
2452Adding Noise to theaddnoise439,16169 2465Adding Noise to theaddnoise439,16607
2453Quantizing the Receivedquantizing469,18632 2466Quantizing the Receivedquantizing469,19100
2454 2467
2455html-src/software.html,439 2468html-src/software.html,439
2456Francesco Potortì Software Page9,280 2469Francesco Potortì Software Page9,280
diff --git a/test/etags/ETAGS.good_5 b/test/etags/ETAGS.good_5
index 526ad4079b8..d84017245c9 100644
--- a/test/etags/ETAGS.good_5
+++ b/test/etags/ETAGS.good_5
@@ -739,6 +739,19 @@ char **tab_fill(tab_fill70,1129
739int tab_delete_first(91,1638 739int tab_delete_first(91,1638
740int tab_count_words(103,1820 740int tab_count_words(103,1820
741 741
742c-src/dostorture.c,198
743(*tag1 tag118,468
744#define notag2 26,577
745(*tag2 tag229,657
746(*tag3 tag339,809
747#define notag4 45,904
748(*tag4 tag448,1001
749tag5 57,1136
750tag6 66,1272
751int pp1(74,1389
752pp287,1504
753pp3(100,1616
754
742c-src/emacs/src/gmalloc.c,7311 755c-src/emacs/src/gmalloc.c,7311
743#define USE_PTHREAD25,1002 756#define USE_PTHREAD25,1002
744#undef get_current_dir_name33,1126 757#undef get_current_dir_name33,1126
@@ -2856,61 +2869,61 @@ class AU 53,1716
2856class AU { T x;53,1716 2869class AU { T x;53,1716
2857class B<B54,1735 2870class B<B54,1735
2858class B<int> { void f(54,1735 2871class B<int> { void f(54,1735
2859const A::B::T& abt 55,1765 2872const A::B::T& abt 55,1766
2860class A 56,1791 2873class A 56,1792
2861class A { class B 56,1791 2874class A { class B 56,1792
2862class A { class B { int f(56,1791 2875class A { class B { int f(56,1792
2863class A 57,1826 2876class A 57,1827
2864 int get_data(58,1836 2877 int get_data(58,1837
2865 A operator+(59,1860 2878 A operator+(59,1861
2866is_muldiv_operation(61,1887 2879is_muldiv_operation(61,1888
2867domain foo 68,1955 2880domain foo 68,1956
2868 void f(69,1968 2881 void f(69,1969
2869void A::A(A72,1989 2882void A::A(A72,1990
2870struct A 73,2004 2883struct A 73,2005
2871struct A { A(73,2004 2884struct A { A(73,2005
2872struct B 74,2022 2885struct B 74,2023
2873struct B { B(74,2022 2886struct B { B(74,2023
2874void B::B(B75,2041 2887void B::B(B75,2042
2875void BE_Node::BE_Node(BE_Node76,2056 2888void BE_Node::BE_Node(BE_Node76,2057
2876class BE_Node 77,2083 2889class BE_Node 77,2084
2877struct foo 79,2102 2890struct foo 79,2103
2878 int x;80,2115 2891 int x;80,2116
2879class test 86,2156 2892class test 86,2157
2880 int f(87,2169 2893 int f(87,2170
2881 int ff(89,2231 2894 int ff(89,2232
2882 int g(90,2254 2895 int g(90,2255
2883class AST_Root 92,2278 2896class AST_Root 92,2279
2884class AST_Root;96,2327 2897class AST_Root;96,2328
2885AST_ConcreteType::AST_ConcreteType(99,2393 2898AST_ConcreteType::AST_ConcreteType(99,2394
2886AST_Array::AST_Array(107,2532 2899AST_Array::AST_Array(107,2533
2887 void f(115,2733 2900 void f(115,2734
2888struct A 117,2753 2901struct A 117,2754
2889 ~A(118,2764 2902 ~A(118,2765
2890A::~A(~A120,2777 2903A::~A(~A120,2778
2891struct B 122,2789 2904struct B 122,2790
2892 ~B(123,2800 2905 ~B(123,2801
2893enum {dog,dog126,2817 2906enum {dog,dog126,2818
2894enum {dog, cat}cat126,2817 2907enum {dog, cat}cat126,2818
2895enum {dog, cat} animals;126,2817 2908enum {dog, cat} animals;126,2818
2896struct {int teats;127,2842 2909struct {int teats;127,2843
2897struct {int teats;} cow;127,2842 2910struct {int teats;} cow;127,2843
2898class Boo 129,2868 2911class Boo 129,2869
2899 enum {dog,dog130,2880 2912 enum {dog,dog130,2881
2900 enum {dog, cat}cat130,2880 2913 enum {dog, cat}cat130,2881
2901 enum {dog, cat} animals;130,2880 2914 enum {dog, cat} animals;130,2881
2902 struct {int treats;131,2909 2915 struct {int treats;131,2910
2903 struct {int treats;} cow;131,2909 2916 struct {int treats;} cow;131,2910
2904 int i,132,2939 2917 int i,132,2940
2905 int i,a,132,2939 2918 int i,a,132,2940
2906 int i,a,b;132,2939 2919 int i,a,b;132,2940
2907 foo(133,2954 2920 foo(133,2955
2908 Boo(137,2995 2921 Boo(137,2996
2909 Boo(138,3052 2922 Boo(138,3053
2910Boo::Boo(141,3070 2923Boo::Boo(141,3071
2911typedef int should_see_this_one_enclosed_in_extern_C;149,3155 2924typedef int should_see_this_one_enclosed_in_extern_C;149,3156
2912typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3228 2925typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3229
2913typedef int should_see_this_array_type[should_see_this_array_type156,3310 2926typedef int should_see_this_array_type[should_see_this_array_type156,3311
2914 2927
2915cp-src/burton.cpp,124 2928cp-src/burton.cpp,124
2916::dummy::dummy test::dummy1(dummy11,0 2929::dummy::dummy test::dummy1(dummy11,0
@@ -3326,15 +3339,15 @@ Comunicati e iniziative32,976
3326Ultime notizie dall'associazione63,2030 3339Ultime notizie dall'associazione63,2030
3327 3340
3328html-src/algrthms.html,467 3341html-src/algrthms.html,467
3329Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,271 3342Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,277
3330Descriptionalgorithms10,472 3343Descriptionalgorithms10,481
3331Generating the Datagenalgorithm48,1948 3344Generating the Datagenalgorithm48,1995
3332Convolutionallyconalgorithm55,2458 3345Convolutionallyconalgorithm55,2512
3333Nextstatetable262,11326 3346Nextstatetable262,11587
3334Outputoutputtable350,13566 3347Outputoutputtable350,13915
3335Mapping the Channel Symbolsmapping433,15781 3348Mapping the Channel Symbolsmapping433,16213
3336Adding Noise to theaddnoise439,16169 3349Adding Noise to theaddnoise439,16607
3337Quantizing the Receivedquantizing469,18632 3350Quantizing the Receivedquantizing469,19100
3338 3351
3339html-src/software.html,439 3352html-src/software.html,439
3340Francesco Potortì Software Page9,280 3353Francesco Potortì Software Page9,280
diff --git a/test/etags/Makefile b/test/etags/Makefile
index 99ad41ebaab..c305a8b26b9 100644
--- a/test/etags/Makefile
+++ b/test/etags/Makefile
@@ -1,7 +1,7 @@
1ADASRC=$(addprefix ./ada-src/,etags-test-for.ada 2ataspri.adb 2ataspri.ads waroquiers.ada) 1ADASRC=$(addprefix ./ada-src/,etags-test-for.ada 2ataspri.adb 2ataspri.ads waroquiers.ada)
2ASRC=$(addprefix ./a-src/,empty.zz empty.zz.gz) 2ASRC=$(addprefix ./a-src/,empty.zz empty.zz.gz)
3CSRC=$(addprefix ./c-src/,abbrev.c .//c.c torture.c getopt.h etags.c\ 3CSRC=$(addprefix ./c-src/,abbrev.c .//c.c torture.c getopt.h etags.c\
4 exit.c exit.strange_suffix sysdep.h tab.c\ 4 exit.c exit.strange_suffix sysdep.h tab.c dostorture.c\
5 emacs/src/gmalloc.c emacs/src/regex.h emacs/src/keyboard.c emacs/src/lisp.h\ 5 emacs/src/gmalloc.c emacs/src/regex.h emacs/src/keyboard.c emacs/src/lisp.h\
6 machsyscalls.c machsyscalls.h fail.c a/b/b.c) ../etags/c-src/h.h 6 machsyscalls.c machsyscalls.h fail.c a/b/b.c) ../etags/c-src/h.h
7CPSRC=$(addprefix ./cp-src/,c.C burton.cpp burton.cpp\ 7CPSRC=$(addprefix ./cp-src/,c.C burton.cpp burton.cpp\
diff --git a/test/etags/c-src/dostorture.c b/test/etags/c-src/dostorture.c
new file mode 100644
index 00000000000..5190734e0fe
--- /dev/null
+++ b/test/etags/c-src/dostorture.c
@@ -0,0 +1,107 @@
1/* Date: Thu, 05 Aug 1993 20:28:03 +0200
2 From: "Tom R.Hageman" <tom@basil.icce.rug.nl>
3 Subject: more etags torture;-) [etags 7.3 patch#3]
4 To: pot@CNUCE.CNR.IT
5
6 Hi,
7
8 This test file illustrates some more problems with etags (7.3):
9
10
11 1. parentheses are confusing,
12 2. preprocessor directives can disrupt other state machines. */
13
14/* A small torture test for etags. */
15
16/* The classic parenthesis nightmare, based on signal(). */
17void
18(*tag1 (sig, handler)) ()
19 int sig;
20 void (*handler) ();
21{
22 (*handler)(sig);
23 return handler;
24}
25
26#define notag2 void
27/* The classic, with user-defined return type. */
28notag2
29(*tag2 (sig, handler)) ()
30 int sig;
31 void (*handler) ();
32{
33 (*handler)(sig);
34 return handler;
35}
36
37/* The classic, in ANSI C style. */
38void
39(*tag3 (int sig, void (*handler) (int))) (int)
40{
41 (*handler)(sig);
42 return handler;
43}
44
45#define notag4 void
46/* The classic, with user-defined return type, in ANSI C style. */
47notag4
48(*tag4 (int sig, void (*handler) (int))) (int)
49{
50 (*handler)(sig);
51 return handler;
52}
53
54
55/* A less tortuous example. */
56void
57tag5 (handler, arg)
58void (*handler)();
59void *arg;
60{
61 (*handler)(arg);
62}
63
64/* A less tortuous example, in ANSI C style. */
65void
66tag6 (void (*handler) (void *), void *arg)
67{
68 (*handler)(arg);
69}
70
71
72/* Interfering preprocessing torture */
73
74int pp1(
75#if (__STDC__)
76 int
77#endif
78 bar)
79#if (!__STDC__)
80 int bar;
81#endif
82{
83 return bar;
84}
85
86int
87pp2
88#if __STDC__
89 (int bar)
90#else
91 (bar)
92 int bar;
93#endif
94{
95 return bar;
96}
97
98int
99#if __STDC__
100pp3(int bar)
101#else
102pp3(bar)
103 int bar;
104#endif
105{
106 return bar;
107}
diff --git a/test/etags/cp-src/c.C b/test/etags/cp-src/c.C
index dae933a9a05..2c5f7e01fac 100644
--- a/test/etags/cp-src/c.C
+++ b/test/etags/cp-src/c.C
@@ -51,7 +51,7 @@ int A<int>::f(A<int>* x) {}
51A<float,B<int> > A<B<float>,int>::f(A<int>* x) {} 51A<float,B<int> > A<B<float>,int>::f(A<int>* x) {}
52template <class C, int n> class AT { C t[n]; }; 52template <class C, int n> class AT { C t[n]; };
53class AU { T x; }; 53class AU { T x; };
54class B<int> { void f() {} }; 54class B<int> { void f() {} };
55const A::B::T& abt = abc; 55const A::B::T& abt = abc;
56class A { class B { int f(); }; }; 56class A { class B { int f(); }; };
57class A { 57class A {
diff --git a/test/etags/html-src/algrthms.html b/test/etags/html-src/algrthms.html
index f051505263c..becd93a62d0 100644
--- a/test/etags/html-src/algrthms.html
+++ b/test/etags/html-src/algrthms.html
@@ -1,519 +1,519 @@
1<!doctype html public "-//w3c//dtd html 4.0 transitional//en"> 1<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
2<html> 2<html>
3<head> 3<head>
4 <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> 4 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
5 <meta name="Author" content="Chip Fleming"> 5 <meta name="Author" content="Chip Fleming">
6 <meta name="GENERATOR" content="Mozilla/4.7 [en] (Win95; U) [Netscape]"> 6 <meta name="GENERATOR" content="Mozilla/4.7 [en] (Win95; U) [Netscape]">
7 <title>Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms</title> 7 <title>Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms</title>
8</head> 8</head>
9<body> 9<body>
10<a NAME="algorithms"></a><b><font face="Arial"><font size=+1>Description 10<a NAME="algorithms"></a><b><font face="Arial"><font size=+1>Description
11of the Algorithms&nbsp; (Part 1)</font></font></b> 11of the Algorithms&nbsp; (Part 1)</font></font></b>
12<p>&nbsp;The steps involved in simulating a communication channel using 12<p>&nbsp;The steps involved in simulating a communication channel using
13convolutional encoding and Viterbi decoding are as follows: 13convolutional encoding and Viterbi decoding are as follows:
14<ul> 14<ul>
15<li> 15<li>
16<a href="#genalgorithm">Generate the data</a> to be transmitted through 16<a href="#genalgorithm">Generate the data</a> to be transmitted through
17the channel-result is binary data bits</li> 17the channel-result is binary data bits</li>
18 18
19<li> 19<li>
20<a href="#conalgorithm">Convolutionally encode</a> the data-result is channel 20<a href="#conalgorithm">Convolutionally encode</a> the data-result is channel
21symbols</li> 21symbols</li>
22 22
23<li> 23<li>
24<a href="#mapping">Map the one/zero channel symbols</a> onto an antipodal 24<a href="#mapping">Map the one/zero channel symbols</a> onto an antipodal
25baseband signal, producing transmitted channel symbols</li> 25baseband signal, producing transmitted channel symbols</li>
26 26
27<li> 27<li>
28<a href="#addnoise">Add noise</a> to the transmitted channel symbols-result 28<a href="#addnoise">Add noise</a> to the transmitted channel symbols-result
29is received channel symbols</li> 29is received channel symbols</li>
30 30
31<li> 31<li>
32<a href="#quantizing">Quantize</a> the received channel levels-one bit 32<a href="#quantizing">Quantize</a> the received channel levels-one bit
33quantization is called hard-decision, and two to n bit quantization is 33quantization is called hard-decision, and two to n bit quantization is
34called soft-decision (n is usually three or four)</li> 34called soft-decision (n is usually three or four)</li>
35 35
36<li> 36<li>
37<a href="algrthms2.html">Perform Viterbi decoding</a> on the quantized 37<a href="algrthms2.html">Perform Viterbi decoding</a> on the quantized
38received channel symbols-result is again binary data bits</li> 38received channel symbols-result is again binary data bits</li>
39 39
40<li> 40<li>
41Compare the decoded data bits to the transmitted data bits and count the 41Compare the decoded data bits to the transmitted data bits and count the
42number of errors.</li> 42number of errors.</li>
43</ul> 43</ul>
44<i>Many of you will notice that I left out the steps of modulating the 44<i>Many of you will notice that I left out the steps of modulating the
45channel symbols onto a transmitted carrier, and then demodulating the received 45channel symbols onto a transmitted carrier, and then demodulating the received
46carrier to recover the channel symbols. You're right, but we can accurately 46carrier to recover the channel symbols. You're right, but we can accurately
47model the effects of AWGN even though we bypass those steps.</i> 47model the effects of AWGN even though we bypass those steps.</i>
48<p><a NAME="genalgorithm"></a><b><i><font face="Arial">Generating the Data</font></i></b> 48<p><a NAME="genalgorithm"></a><b><i><font face="Arial">Generating the Data</font></i></b>
49<p>Generating the data to be transmitted through the channel can be accomplished 49<p>Generating the data to be transmitted through the channel can be accomplished
50quite simply by using a random number generator. One that produces a uniform 50quite simply by using a random number generator. One that produces a uniform
51distribution of numbers on the interval 0 to a maximum value is provided 51distribution of numbers on the interval 0 to a maximum value is provided
52in C: <tt>rand ()</tt>. Using this function, we can say that any value 52in C: <tt>rand ()</tt>. Using this function, we can say that any value
53less than half of the maximum value is a zero; any value greater than or 53less than half of the maximum value is a zero; any value greater than or
54equal to half of the maximum value is a one. 54equal to half of the maximum value is a one.
55<p><a NAME="conalgorithm"></a><b><i><font face="Arial">Convolutionally 55<p><a NAME="conalgorithm"></a><b><i><font face="Arial">Convolutionally
56Encoding the Data</font></i></b> 56Encoding the Data</font></i></b>
57<p>Convolutionally encoding the data is accomplished using a shift register 57<p>Convolutionally encoding the data is accomplished using a shift register
58and associated combinatorial logic that performs modulo-two addition. (A 58and associated combinatorial logic that performs modulo-two addition. (A
59shift register is merely a chain of flip-flops wherein the output of the 59shift register is merely a chain of flip-flops wherein the output of the
60nth flip-flop is tied to the input of the (n+1)th flip-flop. Every time 60nth flip-flop is tied to the input of the (n+1)th flip-flop. Every time
61the active edge of the clock occurs, the input to the flip-flop is clocked 61the active edge of the clock occurs, the input to the flip-flop is clocked
62through to the output, and thus the data are shifted over one stage.) The 62through to the output, and thus the data are shifted over one stage.) The
63combinatorial logic is often in the form of cascaded exclusive-or gates. 63combinatorial logic is often in the form of cascaded exclusive-or gates.
64As a reminder, exclusive-or gates are two-input, one-output gates often 64As a reminder, exclusive-or gates are two-input, one-output gates often
65represented by the logic symbol shown below, 65represented by the logic symbol shown below,
66<center> 66<center>
67<p><img SRC="figs/xor_gate.gif" ALT="exclusive-or gate symbol" height=64 width=93></center> 67<p><img SRC="figs/xor_gate.gif" ALT="exclusive-or gate symbol" height=64 width=93></center>
68 68
69<p>that implement the following truth-table: 69<p>that implement the following truth-table:
70<br>&nbsp; 70<br>&nbsp;
71<br>&nbsp; 71<br>&nbsp;
72<center><table BORDER CELLPADDING=7 WIDTH="218" > 72<center><table BORDER CELLPADDING=7 WIDTH="218" >
73<tr> 73<tr>
74<td VALIGN=TOP WIDTH="28%"> 74<td VALIGN=TOP WIDTH="28%">
75<center><b><tt>Input A</tt></b></center> 75<center><b><tt>Input A</tt></b></center>
76</td> 76</td>
77 77
78<td VALIGN=TOP WIDTH="27%"> 78<td VALIGN=TOP WIDTH="27%">
79<center><b><tt>Input B</tt></b></center> 79<center><b><tt>Input B</tt></b></center>
80</td> 80</td>
81 81
82<td VALIGN=TOP WIDTH="45%"> 82<td VALIGN=TOP WIDTH="45%">
83<center><b><tt>Output</tt></b> 83<center><b><tt>Output</tt></b>
84<p><b><tt>(A xor B)</tt></b></center> 84<p><b><tt>(A xor B)</tt></b></center>
85</td> 85</td>
86</tr> 86</tr>
87 87
88<tr> 88<tr>
89<td VALIGN=TOP WIDTH="28%"> 89<td VALIGN=TOP WIDTH="28%">
90<center><tt>0</tt></center> 90<center><tt>0</tt></center>
91</td> 91</td>
92 92
93<td VALIGN=TOP WIDTH="27%"> 93<td VALIGN=TOP WIDTH="27%">
94<center><tt>0</tt></center> 94<center><tt>0</tt></center>
95</td> 95</td>
96 96
97<td VALIGN=TOP WIDTH="45%"> 97<td VALIGN=TOP WIDTH="45%">
98<center><tt>0</tt></center> 98<center><tt>0</tt></center>
99</td> 99</td>
100</tr> 100</tr>
101 101
102<tr> 102<tr>
103<td VALIGN=TOP WIDTH="28%"> 103<td VALIGN=TOP WIDTH="28%">
104<center><tt>0</tt></center> 104<center><tt>0</tt></center>
105</td> 105</td>
106 106
107<td VALIGN=TOP WIDTH="27%"> 107<td VALIGN=TOP WIDTH="27%">
108<center><tt>1</tt></center> 108<center><tt>1</tt></center>
109</td> 109</td>
110 110
111<td VALIGN=TOP WIDTH="45%"> 111<td VALIGN=TOP WIDTH="45%">
112<center><tt>1</tt></center> 112<center><tt>1</tt></center>
113</td> 113</td>
114</tr> 114</tr>
115 115
116<tr> 116<tr>
117<td VALIGN=TOP WIDTH="28%"> 117<td VALIGN=TOP WIDTH="28%">
118<center><tt>1</tt></center> 118<center><tt>1</tt></center>
119</td> 119</td>
120 120
121<td VALIGN=TOP WIDTH="27%"> 121<td VALIGN=TOP WIDTH="27%">
122<center><tt>0</tt></center> 122<center><tt>0</tt></center>
123</td> 123</td>
124 124
125<td VALIGN=TOP WIDTH="45%"> 125<td VALIGN=TOP WIDTH="45%">
126<center><tt>1</tt></center> 126<center><tt>1</tt></center>
127</td> 127</td>
128</tr> 128</tr>
129 129
130<tr> 130<tr>
131<td VALIGN=TOP WIDTH="28%"> 131<td VALIGN=TOP WIDTH="28%">
132<center><tt>1</tt></center> 132<center><tt>1</tt></center>
133</td> 133</td>
134 134
135<td VALIGN=TOP WIDTH="27%"> 135<td VALIGN=TOP WIDTH="27%">
136<center><tt>1</tt></center> 136<center><tt>1</tt></center>
137</td> 137</td>
138 138
139<td VALIGN=TOP WIDTH="45%"> 139<td VALIGN=TOP WIDTH="45%">
140<center><tt>0</tt></center> 140<center><tt>0</tt></center>
141</td> 141</td>
142</tr> 142</tr>
143</table></center> 143</table></center>
144 144
145<p>The exclusive-or gate performs modulo-two addition of its inputs. When 145<p>The exclusive-or gate performs modulo-two addition of its inputs. When
146you cascade q two-input exclusive-or gates, with the output of the first 146you cascade q two-input exclusive-or gates, with the output of the first
147one feeding one of the inputs of the second one, the output of the second 147one feeding one of the inputs of the second one, the output of the second
148one feeding one of the inputs of the third one, etc., the output of the 148one feeding one of the inputs of the third one, etc., the output of the
149last one in the chain is the modulo-two sum of the q + 1 inputs. 149last one in the chain is the modulo-two sum of the q + 1 inputs.
150<p>Another way to illustrate the modulo-two adder, and the way that is 150<p>Another way to illustrate the modulo-two adder, and the way that is
151most commonly used in textbooks, is as a circle with a + symbol inside, 151most commonly used in textbooks, is as a circle with a + symbol inside,
152thus: 152thus:
153<center> 153<center>
154<p><img SRC="figs/ringsum.gif" ALT="modulo-two adder symbol" height=48 width=48></center> 154<p><img SRC="figs/ringsum.gif" ALT="modulo-two adder symbol" height=48 width=48></center>
155 155
156<p>Now that we have the two basic components of the convolutional encoder 156<p>Now that we have the two basic components of the convolutional encoder
157(flip-flops comprising the shift register and exclusive-or gates comprising 157(flip-flops comprising the shift register and exclusive-or gates comprising
158the associated modulo-two adders) defined, let's look at a picture of a 158the associated modulo-two adders) defined, let's look at a picture of a
159convolutional encoder for a rate 1/2, K = 3, m = 2 code: 159convolutional encoder for a rate 1/2, K = 3, m = 2 code:
160<br>&nbsp; 160<br>&nbsp;
161<br>&nbsp; 161<br>&nbsp;
162<br> 162<br>
163<center> 163<center>
164<p><img SRC="figs/ce_7_5_a.gif" ALT="rate 1/2 K = 3 (7, 5) convolutional encoder" height=232 width=600></center> 164<p><img SRC="figs/ce_7_5_a.gif" ALT="rate 1/2 K = 3 (7, 5) convolutional encoder" height=232 width=600></center>
165 165
166<p>In this encoder, data bits are provided at a rate of k bits per second. 166<p>In this encoder, data bits are provided at a rate of k bits per second.
167Channel symbols are output at a rate of n = 2k symbols per second. The 167Channel symbols are output at a rate of n = 2k symbols per second. The
168input bit is stable during the encoder cycle. The encoder cycle starts 168input bit is stable during the encoder cycle. The encoder cycle starts
169when an input clock edge occurs. When the input clock edge occurs, the 169when an input clock edge occurs. When the input clock edge occurs, the
170output of the left-hand flip-flop is clocked into the right-hand flip-flop, 170output of the left-hand flip-flop is clocked into the right-hand flip-flop,
171the previous input bit is clocked into the left-hand flip-flop, and a new 171the previous input bit is clocked into the left-hand flip-flop, and a new
172input bit becomes available. Then the outputs of the upper and lower modulo-two 172input bit becomes available. Then the outputs of the upper and lower modulo-two
173adders become stable. The output selector (SEL A/B block) cycles through 173adders become stable. The output selector (SEL A/B block) cycles through
174two states-in the first state, it selects and outputs the output of the 174two states-in the first state, it selects and outputs the output of the
175upper modulo-two adder; in the second state, it selects and outputs the 175upper modulo-two adder; in the second state, it selects and outputs the
176output of the lower modulo-two adder. 176output of the lower modulo-two adder.
177<p>The encoder shown above encodes the K = 3, (7, 5) convolutional code. 177<p>The encoder shown above encodes the K = 3, (7, 5) convolutional code.
178The octal numbers 7 and 5 represent the code generator polynomials, which 178The octal numbers 7 and 5 represent the code generator polynomials, which
179when read in binary (111<sub>2</sub> and 101<sub>2</sub>) correspond to 179when read in binary (111<sub>2</sub> and 101<sub>2</sub>) correspond to
180the shift register connections to the upper and lower modulo-two adders, 180the shift register connections to the upper and lower modulo-two adders,
181respectively. This code has been determined to be the "best" code for rate 181respectively. This code has been determined to be the "best" code for rate
1821/2, K = 3. It is the code I will use for the remaining discussion and 1821/2, K = 3. It is the code I will use for the remaining discussion and
183examples, for reasons that will become readily apparent when we get into 183examples, for reasons that will become readily apparent when we get into
184the Viterbi decoder algorithm. 184the Viterbi decoder algorithm.
185<p>Let's look at an example input data stream, and the corresponding output 185<p>Let's look at an example input data stream, and the corresponding output
186data stream: 186data stream:
187<p>Let the input sequence be 010111001010001<sub>2</sub>. 187<p>Let the input sequence be 010111001010001<sub>2</sub>.
188<p>Assume that the outputs of both of the flip-flops in the shift register 188<p>Assume that the outputs of both of the flip-flops in the shift register
189are initially cleared, i.e. their outputs are zeroes. The first clock cycle 189are initially cleared, i.e. their outputs are zeroes. The first clock cycle
190makes the first input bit, a zero, available to the encoder. The flip-flop 190makes the first input bit, a zero, available to the encoder. The flip-flop
191outputs are both zeroes. The inputs to the modulo-two adders are all zeroes, 191outputs are both zeroes. The inputs to the modulo-two adders are all zeroes,
192so the output of the encoder is 00<sub>2</sub>. 192so the output of the encoder is 00<sub>2</sub>.
193<p>The second clock cycle makes the second input bit available to the encoder. 193<p>The second clock cycle makes the second input bit available to the encoder.
194The left-hand flip-flop clocks in the previous bit, which was a zero, and 194The left-hand flip-flop clocks in the previous bit, which was a zero, and
195the right-hand flip-flop clocks in the zero output by the left-hand flip-flop. 195the right-hand flip-flop clocks in the zero output by the left-hand flip-flop.
196The inputs to the top modulo-two adder are 100<sub>2</sub>, so the output 196The inputs to the top modulo-two adder are 100<sub>2</sub>, so the output
197is a one. The inputs to the bottom modulo-two adder are 10<sub>2</sub>, 197is a one. The inputs to the bottom modulo-two adder are 10<sub>2</sub>,
198so the output is also a one. So the encoder outputs 11<sub>2</sub> for 198so the output is also a one. So the encoder outputs 11<sub>2</sub> for
199the channel symbols. 199the channel symbols.
200<p>The third clock cycle makes the third input bit, a zero, available to 200<p>The third clock cycle makes the third input bit, a zero, available to
201the encoder. The left-hand flip-flop clocks in the previous bit, which 201the encoder. The left-hand flip-flop clocks in the previous bit, which
202was a one, and the right-hand flip-flop clocks in the zero from two bit-times 202was a one, and the right-hand flip-flop clocks in the zero from two bit-times
203ago. The inputs to the top modulo-two adder are 010<sub>2</sub>, so the 203ago. The inputs to the top modulo-two adder are 010<sub>2</sub>, so the
204output is a one. The inputs to the bottom modulo-two adder are 00<sub>2</sub>, 204output is a one. The inputs to the bottom modulo-two adder are 00<sub>2</sub>,
205so the output is zero. So the encoder outputs 10<sub>2</sub> for the channel 205so the output is zero. So the encoder outputs 10<sub>2</sub> for the channel
206symbols. 206symbols.
207<p>And so on. The timing diagram shown below illustrates the process: 207<p>And so on. The timing diagram shown below illustrates the process:
208<br>&nbsp; 208<br>&nbsp;
209<br>&nbsp; 209<br>&nbsp;
210<br> 210<br>
211<center> 211<center>
212<p><img SRC="figs/ce_td.gif" ALT="timing diagram for rate 1/2 convolutional encoder" height=322 width=600></center> 212<p><img SRC="figs/ce_td.gif" ALT="timing diagram for rate 1/2 convolutional encoder" height=322 width=600></center>
213 213
214<p><br> 214<p><br>
215<br> 215<br>
216<br> 216<br>
217<p>After all of the inputs have been presented to the encoder, the output 217<p>After all of the inputs have been presented to the encoder, the output
218sequence will be: 218sequence will be:
219<p>00 11 10 00 01 10 01 11 11 10 00 10 11 00 11<sub>2</sub>. 219<p>00 11 10 00 01 10 01 11 11 10 00 10 11 00 11<sub>2</sub>.
220<p>Notice that I have paired the encoder outputs-the first bit in each 220<p>Notice that I have paired the encoder outputs-the first bit in each
221pair is the output of the upper modulo-two adder; the second bit in each 221pair is the output of the upper modulo-two adder; the second bit in each
222pair is the output of the lower modulo-two adder. 222pair is the output of the lower modulo-two adder.
223<p>You can see from the structure of the rate 1/2 K = 3 convolutional encoder 223<p>You can see from the structure of the rate 1/2 K = 3 convolutional encoder
224and from the example given above that each input bit has an effect on three 224and from the example given above that each input bit has an effect on three
225successive pairs of output symbols. That is an extremely important point 225successive pairs of output symbols. That is an extremely important point
226and that is what gives the convolutional code its error-correcting power. 226and that is what gives the convolutional code its error-correcting power.
227The reason why will become evident when we get into the Viterbi decoder 227The reason why will become evident when we get into the Viterbi decoder
228algorithm. 228algorithm.
229<p>Now if we are only going to send the 15 data bits given above, in order 229<p>Now if we are only going to send the 15 data bits given above, in order
230for the last bit to affect three pairs of output symbols, we need to output 230for the last bit to affect three pairs of output symbols, we need to output
231two more pairs of symbols. This is accomplished in our example encoder 231two more pairs of symbols. This is accomplished in our example encoder
232by clocking the convolutional encoder flip-flops two ( = m) more times, 232by clocking the convolutional encoder flip-flops two ( = m) more times,
233while holding the input at zero. This is called "flushing" the encoder, 233while holding the input at zero. This is called "flushing" the encoder,
234and results in two more pairs of output symbols. The final binary output 234and results in two more pairs of output symbols. The final binary output
235of the encoder is thus 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11 10 235of the encoder is thus 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11 10
23611<sub>2</sub>. If we don't perform the flushing operation, the last m 23611<sub>2</sub>. If we don't perform the flushing operation, the last m
237bits of the message have less error-correction capability than the first 237bits of the message have less error-correction capability than the first
238through (m - 1)th bits had. This is a pretty important thing to remember 238through (m - 1)th bits had. This is a pretty important thing to remember
239if you're going to use this FEC technique in a burst-mode environment. 239if you're going to use this FEC technique in a burst-mode environment.
240So's the step of clearing the shift register at the beginning of each burst. 240So's the step of clearing the shift register at the beginning of each burst.
241The encoder must start in a known state and end in a known state for the 241The encoder must start in a known state and end in a known state for the
242decoder to be able to reconstruct the input data sequence properly. 242decoder to be able to reconstruct the input data sequence properly.
243<p>Now, let's look at the encoder from another perspective. You can think 243<p>Now, let's look at the encoder from another perspective. You can think
244of the encoder as a simple state machine. The example encoder has two bits 244of the encoder as a simple state machine. The example encoder has two bits
245of memory, so there are four possible states. Let's give the left-hand 245of memory, so there are four possible states. Let's give the left-hand
246flip-flop a binary weight of 2<sup>1</sup>, and the right-hand flip-flop 246flip-flop a binary weight of 2<sup>1</sup>, and the right-hand flip-flop
247a binary weight of 2<sup>0</sup>. Initially, the encoder is in the all-zeroes 247a binary weight of 2<sup>0</sup>. Initially, the encoder is in the all-zeroes
248state. If the first input bit is a zero, the encoder stays in the all zeroes 248state. If the first input bit is a zero, the encoder stays in the all zeroes
249state at the next clock edge. But if the input bit is a one, the encoder 249state at the next clock edge. But if the input bit is a one, the encoder
250transitions to the 10<sub>2</sub> state at the next clock edge. Then, if 250transitions to the 10<sub>2</sub> state at the next clock edge. Then, if
251the next input bit is zero, the encoder transitions to the 01<sub>2</sub> 251the next input bit is zero, the encoder transitions to the 01<sub>2</sub>
252state, otherwise, it transitions to the 11<sub>2</sub> state. The following 252state, otherwise, it transitions to the 11<sub>2</sub> state. The following
253table gives the next state given the current state and the input, with 253table gives the next state given the current state and the input, with
254the states given in binary: 254the states given in binary:
255<br>&nbsp; 255<br>&nbsp;
256<br>&nbsp; 256<br>&nbsp;
257<center><table BORDER CELLSPACING=2 CELLPADDING=7 WIDTH="282" > 257<center><table BORDER CELLSPACING=2 CELLPADDING=7 WIDTH="282" >
258<tr> 258<tr>
259<td VALIGN=TOP WIDTH="33%"><font face="Arial"><font size=-1>&nbsp;</font></font></td> 259<td VALIGN=TOP WIDTH="33%"><font face="Arial"><font size=-1>&nbsp;</font></font></td>
260 260
261<td VALIGN=TOP COLSPAN="2" WIDTH="67%"> 261<td VALIGN=TOP COLSPAN="2" WIDTH="67%">
262<center><a NAME="statetable"></a><b><font face="Arial"><font size=-1>Next 262<center><a NAME="statetable"></a><b><font face="Arial"><font size=-1>Next
263State, if&nbsp;</font></font></b></center> 263State, if&nbsp;</font></font></b></center>
264</td> 264</td>
265</tr> 265</tr>
266 266
267<tr> 267<tr>
268<td VALIGN=TOP WIDTH="33%"> 268<td VALIGN=TOP WIDTH="33%">
269<center><b><font face="Arial"><font size=-1>Current State</font></font></b></center> 269<center><b><font face="Arial"><font size=-1>Current State</font></font></b></center>
270</td> 270</td>
271 271
272<td VALIGN=TOP WIDTH="33%"> 272<td VALIGN=TOP WIDTH="33%">
273<center><b><font face="Arial"><font size=-1>Input = 0:</font></font></b></center> 273<center><b><font face="Arial"><font size=-1>Input = 0:</font></font></b></center>
274</td> 274</td>
275 275
276<td VALIGN=TOP WIDTH="33%"> 276<td VALIGN=TOP WIDTH="33%">
277<center><b><font face="Arial"><font size=-1>Input = 1:</font></font></b></center> 277<center><b><font face="Arial"><font size=-1>Input = 1:</font></font></b></center>
278</td> 278</td>
279</tr> 279</tr>
280 280
281<tr> 281<tr>
282<td VALIGN=TOP WIDTH="33%"> 282<td VALIGN=TOP WIDTH="33%">
283<center><font face="Arial"><font size=-1>00</font></font></center> 283<center><font face="Arial"><font size=-1>00</font></font></center>
284</td> 284</td>
285 285
286<td VALIGN=TOP WIDTH="33%"> 286<td VALIGN=TOP WIDTH="33%">
287<center><font face="Arial"><font size=-1>00</font></font></center> 287<center><font face="Arial"><font size=-1>00</font></font></center>
288</td> 288</td>
289 289
290<td VALIGN=TOP WIDTH="33%"> 290<td VALIGN=TOP WIDTH="33%">
291<center><font face="Arial"><font size=-1>10</font></font></center> 291<center><font face="Arial"><font size=-1>10</font></font></center>
292</td> 292</td>
293</tr> 293</tr>
294 294
295<tr> 295<tr>
296<td VALIGN=TOP WIDTH="33%"> 296<td VALIGN=TOP WIDTH="33%">
297<center><font face="Arial"><font size=-1>01</font></font></center> 297<center><font face="Arial"><font size=-1>01</font></font></center>
298</td> 298</td>
299 299
300<td VALIGN=TOP WIDTH="33%"> 300<td VALIGN=TOP WIDTH="33%">
301<center><font face="Arial"><font size=-1>00</font></font></center> 301<center><font face="Arial"><font size=-1>00</font></font></center>
302</td> 302</td>
303 303
304<td VALIGN=TOP WIDTH="33%"> 304<td VALIGN=TOP WIDTH="33%">
305<center><font face="Arial"><font size=-1>10</font></font></center> 305<center><font face="Arial"><font size=-1>10</font></font></center>
306</td> 306</td>
307</tr> 307</tr>
308 308
309<tr> 309<tr>
310<td VALIGN=TOP WIDTH="33%"> 310<td VALIGN=TOP WIDTH="33%">
311<center><font face="Arial"><font size=-1>10</font></font></center> 311<center><font face="Arial"><font size=-1>10</font></font></center>
312</td> 312</td>
313 313
314<td VALIGN=TOP WIDTH="33%"> 314<td VALIGN=TOP WIDTH="33%">
315<center><font face="Arial"><font size=-1>01</font></font></center> 315<center><font face="Arial"><font size=-1>01</font></font></center>
316</td> 316</td>
317 317
318<td VALIGN=TOP WIDTH="33%"> 318<td VALIGN=TOP WIDTH="33%">
319<center><font face="Arial"><font size=-1>11</font></font></center> 319<center><font face="Arial"><font size=-1>11</font></font></center>
320</td> 320</td>
321</tr> 321</tr>
322 322
323<tr> 323<tr>
324<td VALIGN=TOP WIDTH="33%"> 324<td VALIGN=TOP WIDTH="33%">
325<center><font face="Arial"><font size=-1>11</font></font></center> 325<center><font face="Arial"><font size=-1>11</font></font></center>
326</td> 326</td>
327 327
328<td VALIGN=TOP WIDTH="33%"> 328<td VALIGN=TOP WIDTH="33%">
329<center><font face="Arial"><font size=-1>01</font></font></center> 329<center><font face="Arial"><font size=-1>01</font></font></center>
330</td> 330</td>
331 331
332<td VALIGN=TOP WIDTH="33%"> 332<td VALIGN=TOP WIDTH="33%">
333<center><font face="Arial"><font size=-1>11</font></font></center> 333<center><font face="Arial"><font size=-1>11</font></font></center>
334</td> 334</td>
335</tr> 335</tr>
336</table></center> 336</table></center>
337 337
338<br>&nbsp; 338<br>&nbsp;
339<p>The above table is often called a state transition table. We'll refer 339<p>The above table is often called a state transition table. We'll refer
340to it as the <tt>next state</tt> table.<tt> </tt>Now let us look at a table 340to it as the <tt>next state</tt> table.<tt> </tt>Now let us look at a table
341that lists the channel output symbols, given the current state and the 341that lists the channel output symbols, given the current state and the
342input data, which we'll refer to as the <tt>output</tt> table: 342input data, which we'll refer to as the <tt>output</tt> table:
343<br>&nbsp; 343<br>&nbsp;
344<br>&nbsp; 344<br>&nbsp;
345<center><table BORDER CELLSPACING=2 CELLPADDING=7 WIDTH="282" > 345<center><table BORDER CELLSPACING=2 CELLPADDING=7 WIDTH="282" >
346<tr> 346<tr>
347<td VALIGN=TOP WIDTH="33%"></td> 347<td VALIGN=TOP WIDTH="33%"></td>
348 348
349<td VALIGN=TOP COLSPAN="2" WIDTH="67%"> 349<td VALIGN=TOP COLSPAN="2" WIDTH="67%">
350<center><a NAME="outputtable"></a><b><font face="Arial"><font size=-1>Output 350<center><a NAME="outputtable"></a><b><font face="Arial"><font size=-1>Output
351Symbols, if</font></font></b></center> 351Symbols, if</font></font></b></center>
352</td> 352</td>
353</tr> 353</tr>
354 354
355<tr> 355<tr>
356<td VALIGN=TOP WIDTH="33%"> 356<td VALIGN=TOP WIDTH="33%">
357<center><b><font face="Arial"><font size=-1>Current State</font></font></b></center> 357<center><b><font face="Arial"><font size=-1>Current State</font></font></b></center>
358</td> 358</td>
359 359
360<td VALIGN=TOP WIDTH="33%"> 360<td VALIGN=TOP WIDTH="33%">
361<center><b><font face="Arial"><font size=-1>Input = 0:</font></font></b></center> 361<center><b><font face="Arial"><font size=-1>Input = 0:</font></font></b></center>
362</td> 362</td>
363 363
364<td VALIGN=TOP WIDTH="33%"> 364<td VALIGN=TOP WIDTH="33%">
365<center><b><font face="Arial"><font size=-1>Input = 1:</font></font></b></center> 365<center><b><font face="Arial"><font size=-1>Input = 1:</font></font></b></center>
366</td> 366</td>
367</tr> 367</tr>
368 368
369<tr> 369<tr>
370<td VALIGN=TOP WIDTH="33%"> 370<td VALIGN=TOP WIDTH="33%">
371<center><font face="Arial"><font size=-1>00</font></font></center> 371<center><font face="Arial"><font size=-1>00</font></font></center>
372</td> 372</td>
373 373
374<td VALIGN=TOP WIDTH="33%"> 374<td VALIGN=TOP WIDTH="33%">
375<center><font face="Arial"><font size=-1>00</font></font></center> 375<center><font face="Arial"><font size=-1>00</font></font></center>
376</td> 376</td>
377 377
378<td VALIGN=TOP WIDTH="33%"> 378<td VALIGN=TOP WIDTH="33%">
379<center><font face="Arial"><font size=-1>11</font></font></center> 379<center><font face="Arial"><font size=-1>11</font></font></center>
380</td> 380</td>
381</tr> 381</tr>
382 382
383<tr> 383<tr>
384<td VALIGN=TOP WIDTH="33%"> 384<td VALIGN=TOP WIDTH="33%">
385<center><font face="Arial"><font size=-1>01</font></font></center> 385<center><font face="Arial"><font size=-1>01</font></font></center>
386</td> 386</td>
387 387
388<td VALIGN=TOP WIDTH="33%"> 388<td VALIGN=TOP WIDTH="33%">
389<center><font face="Arial"><font size=-1>11</font></font></center> 389<center><font face="Arial"><font size=-1>11</font></font></center>
390</td> 390</td>
391 391
392<td VALIGN=TOP WIDTH="33%"> 392<td VALIGN=TOP WIDTH="33%">
393<center><font face="Arial"><font size=-1>00</font></font></center> 393<center><font face="Arial"><font size=-1>00</font></font></center>
394</td> 394</td>
395</tr> 395</tr>
396 396
397<tr> 397<tr>
398<td VALIGN=TOP WIDTH="33%"> 398<td VALIGN=TOP WIDTH="33%">
399<center><font face="Arial"><font size=-1>10</font></font></center> 399<center><font face="Arial"><font size=-1>10</font></font></center>
400</td> 400</td>
401 401
402<td VALIGN=TOP WIDTH="33%"> 402<td VALIGN=TOP WIDTH="33%">
403<center><font face="Arial"><font size=-1>10</font></font></center> 403<center><font face="Arial"><font size=-1>10</font></font></center>
404</td> 404</td>
405 405
406<td VALIGN=TOP WIDTH="33%"> 406<td VALIGN=TOP WIDTH="33%">
407<center><font face="Arial"><font size=-1>01</font></font></center> 407<center><font face="Arial"><font size=-1>01</font></font></center>
408</td> 408</td>
409</tr> 409</tr>
410 410
411<tr> 411<tr>
412<td VALIGN=TOP WIDTH="33%"> 412<td VALIGN=TOP WIDTH="33%">
413<center><font face="Arial"><font size=-1>11</font></font></center> 413<center><font face="Arial"><font size=-1>11</font></font></center>
414</td> 414</td>
415 415
416<td VALIGN=TOP WIDTH="33%"> 416<td VALIGN=TOP WIDTH="33%">
417<center><font face="Arial"><font size=-1>01</font></font></center> 417<center><font face="Arial"><font size=-1>01</font></font></center>
418</td> 418</td>
419 419
420<td VALIGN=TOP WIDTH="33%"> 420<td VALIGN=TOP WIDTH="33%">
421<center><font face="Arial"><font size=-1>10</font></font></center> 421<center><font face="Arial"><font size=-1>10</font></font></center>
422</td> 422</td>
423</tr> 423</tr>
424</table></center> 424</table></center>
425 425
426<br>&nbsp; 426<br>&nbsp;
427<p>You should now see that with these two tables, you can completely describe 427<p>You should now see that with these two tables, you can completely describe
428the behavior of the example rate 1/2, K = 3 convolutional encoder. Note 428the behavior of the example rate 1/2, K = 3 convolutional encoder. Note
429that both of these tables have 2<sup>(K - 1)</sup> rows, and 2<sup>k</sup> 429that both of these tables have 2<sup>(K - 1)</sup> rows, and 2<sup>k</sup>
430columns, where K is the constraint length and k is the number of bits input 430columns, where K is the constraint length and k is the number of bits input
431to the encoder for each cycle. These two tables will come in handy when 431to the encoder for each cycle. These two tables will come in handy when
432we start discussing the Viterbi decoder algorithm. 432we start discussing the Viterbi decoder algorithm.
433<p><a NAME="mapping"></a><b><i><font face="Arial">Mapping the Channel Symbols 433<p><a NAME="mapping"></a><b><i><font face="Arial">Mapping the Channel Symbols
434to Signal Levels</font></i></b> 434to Signal Levels</font></i></b>
435<p>Mapping the one/zero output of the convolutional encoder onto an antipodal 435<p>Mapping the one/zero output of the convolutional encoder onto an antipodal
436baseband signaling scheme is simply a matter of translating zeroes to +1s 436baseband signaling scheme is simply a matter of translating zeroes to +1s
437and ones to -1s. This can be accomplished by performing the operation y 437and ones to -1s. This can be accomplished by performing the operation y
438= 1 - 2x on each convolutional encoder output symbol. 438= 1 - 2x on each convolutional encoder output symbol.
439<p><a NAME="addnoise"></a><b><i><font face="Arial">Adding Noise to the 439<p><a NAME="addnoise"></a><b><i><font face="Arial">Adding Noise to the
440Transmitted Symbols</font></i></b> 440Transmitted Symbols</font></i></b>
441<p>Adding noise to the transmitted channel symbols produced by the convolutional 441<p>Adding noise to the transmitted channel symbols produced by the convolutional
442encoder involves generating Gaussian random numbers, scaling the numbers 442encoder involves generating Gaussian random numbers, scaling the numbers
443according to the desired energy per symbol to noise density ratio, E<sub>s</sub>/N<sub>0</sub>, 443according to the desired energy per symbol to noise density ratio, E<sub>s</sub>/N<sub>0</sub>,
444and adding the scaled Gaussian random numbers to the channel symbol values. 444and adding the scaled Gaussian random numbers to the channel symbol values.
445<p>For the uncoded channel, E<sub>s</sub>/N<sub>0 </sub>= E<sub>b</sub>/N<sub>0</sub>, 445<p>For the uncoded channel, E<sub>s</sub>/N<sub>0 </sub>= E<sub>b</sub>/N<sub>0</sub>,
446since there is one channel symbol per bit.&nbsp; However, for the coded 446since there is one channel symbol per bit.&nbsp; However, for the coded
447channel, E<sub>s</sub>/N<sub>0 </sub>= E<sub>b</sub>/N<sub>0</sub> + 10log<sub>10</sub>(k/n).&nbsp; 447channel, E<sub>s</sub>/N<sub>0 </sub>= E<sub>b</sub>/N<sub>0</sub> + 10log<sub>10</sub>(k/n).&nbsp;
448For example, for rate 1/2 coding, E<sub>s</sub>/N<sub>0 </sub>= E<sub>b</sub>/N<sub>0</sub> 448For example, for rate 1/2 coding, E<sub>s</sub>/N<sub>0 </sub>= E<sub>b</sub>/N<sub>0</sub>
449+ 10log<sub>10</sub>(1/2) = E<sub>b</sub>/N<sub>0</sub> - 3.01 dB.&nbsp; 449+ 10log<sub>10</sub>(1/2) = E<sub>b</sub>/N<sub>0</sub> - 3.01 dB.&nbsp;
450Similarly, for rate 2/3 coding, E<sub>s</sub>/N<sub>0 </sub>= E<sub>b</sub>/N<sub>0</sub> 450Similarly, for rate 2/3 coding, E<sub>s</sub>/N<sub>0 </sub>= E<sub>b</sub>/N<sub>0</sub>
451+ 10log<sub>10</sub>(2/3) = E<sub>b</sub>/N<sub>0</sub> - 1.76 dB. 451+ 10log<sub>10</sub>(2/3) = E<sub>b</sub>/N<sub>0</sub> - 1.76 dB.
452<p>The Gaussian random number generator is the only interesting part of 452<p>The Gaussian random number generator is the only interesting part of
453this task. C only provides a uniform random number generator, <tt>rand()</tt>. 453this task. C only provides a uniform random number generator, <tt>rand()</tt>.
454In order to obtain Gaussian random numbers, we take advantage of relationships 454In order to obtain Gaussian random numbers, we take advantage of relationships
455between uniform, Rayleigh, and Gaussian distributions: 455between uniform, Rayleigh, and Gaussian distributions:
456<p>Given a uniform random variable U, a Rayleigh random variable R can 456<p>Given a uniform random variable U, a Rayleigh random variable R can
457be obtained by: 457be obtained by:
458<p><img SRC="figs/eqn01.gif" ALT="equation for Rayleigh random deviate given uniform random deviate" height=30 width=297 align=ABSCENTER> 458<p><img SRC="figs/eqn01.gif" ALT="equation for Rayleigh random deviate given uniform random deviate" height=30 width=297 align=ABSCENTER>
459<p>where&nbsp;<img SRC="figs/eqn02.gif" height=24 width=24 align=ABSCENTER>is 459<p>where&nbsp;<img SRC="figs/eqn02.gif" height=24 width=24 align=ABSCENTER>is
460the variance of the Rayleigh random variable, and given R and a second 460the variance of the Rayleigh random variable, and given R and a second
461uniform random variable V, two Gaussian random variables G and H can be 461uniform random variable V, two Gaussian random variables G and H can be
462obtained by 462obtained by
463<p><i>G</i> = <i>R</i> cos <i>U</i> and <i>H</i> = <i>R</i> sin <i>V</i>. 463<p><i>G</i> = <i>R</i> cos <i>U</i> and <i>H</i> = <i>R</i> sin <i>V</i>.
464<p>In the AWGN channel, the signal is corrupted by additive noise, n(t), 464<p>In the AWGN channel, the signal is corrupted by additive noise, n(t),
465which has the power spectrum <i>No</i>/2 watts/Hz. The variance&nbsp;<img SRC="figs/eqn02.gif" ALT="variance" height=24 width=24 align=ABSBOTTOM>of 465which has the power spectrum <i>No</i>/2 watts/Hz. The variance&nbsp;<img SRC="figs/eqn02.gif" ALT="variance" height=24 width=24 align=ABSBOTTOM>of
466this noise is equal to&nbsp;<img SRC="figs/eqn03.gif" ALT="noise density div by two" height=22 width=38 align=TEXTTOP>. 466this noise is equal to&nbsp;<img SRC="figs/eqn03.gif" ALT="noise density div by two" height=22 width=38 align=TEXTTOP>.
467If we set the energy per symbol <i>E<sub>s</sub></i> equal to 1, then&nbsp;<img SRC="figs/eqn04.gif" ALT="equation relating variance to SNR" height=28 width=110 align=ABSBOTTOM>. 467If we set the energy per symbol <i>E<sub>s</sub></i> equal to 1, then&nbsp;<img SRC="figs/eqn04.gif" ALT="equation relating variance to SNR" height=28 width=110 align=ABSBOTTOM>.
468So&nbsp;<img SRC="figs/eqn05.gif" ALT="equation for AWGN st dev given SNR" height=28 width=139 align=ABSCENTER>. 468So&nbsp;<img SRC="figs/eqn05.gif" ALT="equation for AWGN st dev given SNR" height=28 width=139 align=ABSCENTER>.
469<p><a NAME="quantizing"></a><b><i><font face="Arial">Quantizing the Received 469<p><a NAME="quantizing"></a><b><i><font face="Arial">Quantizing the Received
470Channel Symbols</font></i></b> 470Channel Symbols</font></i></b>
471<p>An ideal Viterbi decoder would work with infinite precision, or at least 471<p>An ideal Viterbi decoder would work with infinite precision, or at least
472with floating-point numbers. In practical systems, we quantize the received 472with floating-point numbers. In practical systems, we quantize the received
473channel symbols with one or a few bits of precision in order to reduce 473channel symbols with one or a few bits of precision in order to reduce
474the complexity of the Viterbi decoder, not to mention the circuits that 474the complexity of the Viterbi decoder, not to mention the circuits that
475precede it. If the received channel symbols are quantized to one-bit precision 475precede it. If the received channel symbols are quantized to one-bit precision
476(&lt; 0V = 1, <u>></u> 0V = 0), the result is called hard-decision data. 476(&lt; 0V = 1, <u>></u> 0V = 0), the result is called hard-decision data.
477If the received channel symbols are quantized with more than one bit of 477If the received channel symbols are quantized with more than one bit of
478precision, the result is called soft-decision data. A Viterbi decoder with 478precision, the result is called soft-decision data. A Viterbi decoder with
479soft decision data inputs quantized to three or four bits of precision 479soft decision data inputs quantized to three or four bits of precision
480can perform about 2 dB better than one working with hard-decision inputs. 480can perform about 2 dB better than one working with hard-decision inputs.
481The usual quantization precision is three bits. More bits provide little 481The usual quantization precision is three bits. More bits provide little
482additional improvement. 482additional improvement.
483<p>The selection of the quantizing levels is an important design decision 483<p>The selection of the quantizing levels is an important design decision
484because it can have a significant effect on the performance of the link. 484because it can have a significant effect on the performance of the link.
485The following is a very brief explanation of one way to set those levels. 485The following is a very brief explanation of one way to set those levels.
486Let's assume our received signal levels in the absence of noise are -1V 486Let's assume our received signal levels in the absence of noise are -1V
487= 1, +1V = 0. With noise, our received signal has mean +/- 1 and standard 487= 1, +1V = 0. With noise, our received signal has mean +/- 1 and standard
488deviation&nbsp;<img SRC="figs/eqn05.gif" ALT="equation for AWGN st dev given SNR" height=28 width=139 align=ABSCENTER>. 488deviation&nbsp;<img SRC="figs/eqn05.gif" ALT="equation for AWGN st dev given SNR" height=28 width=139 align=ABSCENTER>.
489Let's use a uniform, three-bit quantizer having the input/output relationship 489Let's use a uniform, three-bit quantizer having the input/output relationship
490shown in the figure below, where D is a decision level that we will calculate 490shown in the figure below, where D is a decision level that we will calculate
491shortly: 491shortly:
492<center> 492<center>
493<p><img SRC="figs/quantize.gif" ALT="8-level quantizer function plot" height=342 width=384></center> 493<p><img SRC="figs/quantize.gif" ALT="8-level quantizer function plot" height=342 width=384></center>
494 494
495<p>The decision level, D, can be calculated according to the formula&nbsp;<img SRC="figs/eqn06.gif" ALT="equation for quantizer decision level" height=28 width=228 align=ABSCENTER>, 495<p>The decision level, D, can be calculated according to the formula&nbsp;<img SRC="figs/eqn06.gif" ALT="equation for quantizer decision level" height=28 width=228 align=ABSCENTER>,
496where E<sub>s</sub>/N<sub>0</sub> is the energy per symbol to noise density 496where E<sub>s</sub>/N<sub>0</sub> is the energy per symbol to noise density
497ratio<i>. (The above figure was redrawn from Figure 2 of Advanced Hardware 497ratio<i>. (The above figure was redrawn from Figure 2 of Advanced Hardware
498Architecture's ANRS07-0795, "Soft Decision Thresholds and Effects on Viterbi 498Architecture's ANRS07-0795, "Soft Decision Thresholds and Effects on Viterbi
499Performance". See the </i><a href="fecbiblio.html">bibliography</a><i>&nbsp; 499Performance". See the </i><a href="fecbiblio.html">bibliography</a><i>&nbsp;
500for a link to their web pages.)</i> 500for a link to their web pages.)</i>
501<p>Click <a href="algrthms2.html">here</a> to proceed to the description 501<p>Click <a href="algrthms2.html">here</a> to proceed to the description
502of the Viterbi decoding algorithm itself... 502of the Viterbi decoding algorithm itself...
503<p>Or click on one of the links below to go to the beginning of that section: 503<p>Or click on one of the links below to go to the beginning of that section:
504<p>&nbsp;<a href="tutorial.html">Introduction</a> 504<p>&nbsp;<a href="tutorial.html">Introduction</a>
505<br>&nbsp;<a href="algrthms2.html">Description of the Algorithms&nbsp; 505<br>&nbsp;<a href="algrthms2.html">Description of the Algorithms&nbsp;
506(Part 2)</a> 506(Part 2)</a>
507<br>&nbsp;<a href="examples.html">Simulation Source Code Examples</a> 507<br>&nbsp;<a href="examples.html">Simulation Source Code Examples</a>
508<br>&nbsp;<a href="simrslts.html">Example Simulation Results</a> 508<br>&nbsp;<a href="simrslts.html">Example Simulation Results</a>
509<br>&nbsp;<a href="fecbiblio.html">Bibliography</a> 509<br>&nbsp;<a href="fecbiblio.html">Bibliography</a>
510<br>&nbsp;<a href="tutorial.html#specapps">About Spectrum Applications...</a> 510<br>&nbsp;<a href="tutorial.html#specapps">About Spectrum Applications...</a>
511<br>&nbsp; 511<br>&nbsp;
512<br>&nbsp; 512<br>&nbsp;
513<br> 513<br>
514<br> 514<br>
515<center> 515<center>
516<p><img SRC="figs/stripe.gif" height=6 width=600></center> 516<p><img SRC="figs/stripe.gif" height=6 width=600></center>
517 517
518</body> 518</body>
519</html> 519</html>
generated by cgit v1.2.1 (git 2.18.0) at 2026-02-09 20:08:07 +0000