From 5e73eab8faaa6c5198d445d8625db53971300777 Mon Sep 17 00:00:00 2001 From: Eli Zaretskii Date: Sat, 30 May 2015 14:00:06 +0300 Subject: [PATCH] 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. --- test/etags/CTAGS.good | 11 + test/etags/ETAGS.good_1 | 111 +-- test/etags/ETAGS.good_2 | 125 ++-- test/etags/ETAGS.good_3 | 127 ++-- test/etags/ETAGS.good_4 | 111 +-- test/etags/ETAGS.good_5 | 141 ++-- test/etags/Makefile | 2 +- test/etags/c-src/dostorture.c | 107 +++ test/etags/cp-src/c.C | 2 +- test/etags/html-src/algrthms.html | 1038 ++++++++++++++--------------- 10 files changed, 979 insertions(+), 796 deletions(-) create mode 100644 test/etags/c-src/dostorture.c 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 not_eol c-src/emacs/src/regex.h 394 not_single_kboard_state c-src/emacs/src/keyboard.c /^not_single_kboard_state (KBOARD *kboard)$/ notag2 c-src/torture.c 26 +notag2 c-src/dostorture.c 26 notag4 c-src/torture.c 45 +notag4 c-src/dostorture.c 45 notinname c-src/etags.c /^#define notinname(c) (_nin[CHAR (c)]) \/* c is not / npending c-src/emacs/src/keyboard.c 7244 ntool_bar_items c-src/emacs/src/keyboard.c 7974 @@ -3715,8 +3717,11 @@ post pyt-src/server.py /^ def post(self):$/ post pyt-src/server.py /^ def post(self):$/ pot_etags_version c-src/etags.c 81 pp1 c-src/torture.c /^int pp1($/ +pp1 c-src/dostorture.c /^int pp1($/ pp2 c-src/torture.c /^pp2$/ +pp2 c-src/dostorture.c /^pp2$/ pp3 c-src/torture.c /^pp3(int bar)$/ +pp3 c-src/dostorture.c /^pp3(int bar)$/ pp_bas_cat prol-src/natded.prolog /^pp_bas_cat(Cat):-$/ pp_cat prol-src/natded.prolog /^pp_cat(Syn:Sem):-$/ pp_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) tag-symbol-match-p el-src/emacs/lisp/progmodes/etags.el /^(defun tag-symbol-match-p (tag)$/ tag-word-match-p el-src/emacs/lisp/progmodes/etags.el /^(defun tag-word-match-p (tag)$/ tag1 c-src/torture.c /^(*tag1 (sig, handler)) ()$/ +tag1 c-src/dostorture.c /^(*tag1 (sig, handler)) ()$/ tag1 c-src/h.h 110 tag2 c-src/torture.c /^(*tag2 (sig, handler)) ()$/ +tag2 c-src/dostorture.c /^(*tag2 (sig, handler)) ()$/ tag3 c-src/torture.c /^(*tag3 (int sig, void (*handler) (int))) (int)$/ +tag3 c-src/dostorture.c /^(*tag3 (int sig, void (*handler) (int))) (int)$/ tag4 c-src/torture.c /^(*tag4 (int sig, void (*handler) (int))) (int)$/ +tag4 c-src/dostorture.c /^(*tag4 (int sig, void (*handler) (int))) (int)$/ tag5 c-src/torture.c /^tag5 (handler, arg)$/ +tag5 c-src/dostorture.c /^tag5 (handler, arg)$/ tag6 c-src/torture.c /^tag6 (void (*handler) (void *), void *arg)$/ +tag6 c-src/dostorture.c /^tag6 (void (*handler) (void *), void *arg)$/ tag_or_ch c-src/emacs/src/lisp.h 3026 taggedfname c-src/etags.c 207 tags-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 int tab_delete_first(91,1638 int tab_count_words(103,1820 +c-src/dostorture.c,198 +(*tag1 tag118,468 +#define notag2 26,577 +(*tag2 tag229,657 +(*tag3 tag339,809 +#define notag4 45,904 +(*tag4 tag448,1001 +tag5 57,1136 +tag6 66,1272 +int pp1(74,1389 +pp287,1504 +pp3(100,1616 + c-src/emacs/src/gmalloc.c,3539 #define USE_PTHREAD25,1002 #undef get_current_dir_name33,1126 @@ -1896,46 +1909,46 @@ template class AT 52,1668 class AU 53,1716 class B<B54,1735 class B { void f(54,1735 -const A::B::T& abt 55,1765 -class A 56,1791 -class A { class B 56,1791 -class A 57,1826 - A operator+(59,1860 -is_muldiv_operation(61,1887 -domain foo 68,1955 - void f(69,1968 -void A::A(A72,1989 -struct A 73,2004 -struct B 74,2022 -void B::B(B75,2041 -void BE_Node::BE_Node(BE_Node76,2056 -class BE_Node 77,2083 -struct foo 79,2102 -class test 86,2156 - int f(87,2169 - int ff(89,2231 - int g(90,2254 -class AST_Root 92,2278 -AST_ConcreteType::AST_ConcreteType(99,2393 -AST_Array::AST_Array(107,2532 - void f(115,2733 -struct A 117,2753 -A::~A(~A120,2777 -struct B 122,2789 - ~B(123,2800 -enum {dog,dog126,2817 -enum {dog, cat}cat126,2817 -enum {dog, cat} animals;126,2817 -struct {int teats;} cow;127,2842 -class Boo 129,2868 - enum {dog,dog130,2880 - enum {dog, cat}cat130,2880 - foo(133,2954 - Boo(137,2995 -Boo::Boo(141,3070 -typedef int should_see_this_one_enclosed_in_extern_C;149,3155 -typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3228 -typedef int should_see_this_array_type[should_see_this_array_type156,3310 +const A::B::T& abt 55,1766 +class A 56,1792 +class A { class B 56,1792 +class A 57,1827 + A operator+(59,1861 +is_muldiv_operation(61,1888 +domain foo 68,1956 + void f(69,1969 +void A::A(A72,1990 +struct A 73,2005 +struct B 74,2023 +void B::B(B75,2042 +void BE_Node::BE_Node(BE_Node76,2057 +class BE_Node 77,2084 +struct foo 79,2103 +class test 86,2157 + int f(87,2170 + int ff(89,2232 + int g(90,2255 +class AST_Root 92,2279 +AST_ConcreteType::AST_ConcreteType(99,2394 +AST_Array::AST_Array(107,2533 + void f(115,2734 +struct A 117,2754 +A::~A(~A120,2778 +struct B 122,2790 + ~B(123,2801 +enum {dog,dog126,2818 +enum {dog, cat}cat126,2818 +enum {dog, cat} animals;126,2818 +struct {int teats;} cow;127,2843 +class Boo 129,2869 + enum {dog,dog130,2881 + enum {dog, cat}cat130,2881 + foo(133,2955 + Boo(137,2996 +Boo::Boo(141,3071 +typedef int should_see_this_one_enclosed_in_extern_C;149,3156 +typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3229 +typedef int should_see_this_array_type[should_see_this_array_type156,3311 cp-src/burton.cpp,124 ::dummy::dummy test::dummy1(dummy11,0 @@ -2278,15 +2291,15 @@ Comunicati e iniziative32,976 Ultime notizie dall'associazione63,2030 html-src/algrthms.html,467 -Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,271 -Descriptionalgorithms10,472 -Generating the Datagenalgorithm48,1948 -Convolutionallyconalgorithm55,2458 -Nextstatetable262,11326 -Outputoutputtable350,13566 -Mapping the Channel Symbolsmapping433,15781 -Adding Noise to theaddnoise439,16169 -Quantizing the Receivedquantizing469,18632 +Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,277 +Descriptionalgorithms10,481 +Generating the Datagenalgorithm48,1995 +Convolutionallyconalgorithm55,2512 +Nextstatetable262,11587 +Outputoutputtable350,13915 +Mapping the Channel Symbolsmapping433,16213 +Adding Noise to theaddnoise439,16607 +Quantizing the Receivedquantizing469,19100 html-src/software.html,439 Francesco 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 int tab_delete_first(91,1638 int tab_count_words(103,1820 +c-src/dostorture.c,198 +(*tag1 tag118,468 +#define notag2 26,577 +(*tag2 tag229,657 +(*tag3 tag339,809 +#define notag4 45,904 +(*tag4 tag448,1001 +tag5 57,1136 +tag6 66,1272 +int pp1(74,1389 +pp287,1504 +pp3(100,1616 + c-src/emacs/src/gmalloc.c,6643 #define USE_PTHREAD25,1002 #undef get_current_dir_name33,1126 @@ -2402,53 +2415,53 @@ template class AT 52,1668 class AU 53,1716 class B<B54,1735 class B { void f(54,1735 -const A::B::T& abt 55,1765 -class A 56,1791 -class A { class B 56,1791 -class A { class B { int f(56,1791 -class A 57,1826 - int get_data(58,1836 - A operator+(59,1860 -is_muldiv_operation(61,1887 -domain foo 68,1955 - void f(69,1968 -void A::A(A72,1989 -struct A 73,2004 -struct A { A(73,2004 -struct B 74,2022 -struct B { B(74,2022 -void B::B(B75,2041 -void BE_Node::BE_Node(BE_Node76,2056 -class BE_Node 77,2083 -struct foo 79,2102 -class test 86,2156 - int f(87,2169 - int ff(89,2231 - int g(90,2254 -class AST_Root 92,2278 -class AST_Root;96,2327 -AST_ConcreteType::AST_ConcreteType(99,2393 -AST_Array::AST_Array(107,2532 - void f(115,2733 -struct A 117,2753 - ~A(118,2764 -A::~A(~A120,2777 -struct B 122,2789 - ~B(123,2800 -enum {dog,dog126,2817 -enum {dog, cat}cat126,2817 -enum {dog, cat} animals;126,2817 -struct {int teats;} cow;127,2842 -class Boo 129,2868 - enum {dog,dog130,2880 - enum {dog, cat}cat130,2880 - foo(133,2954 - Boo(137,2995 - Boo(138,3052 -Boo::Boo(141,3070 -typedef int should_see_this_one_enclosed_in_extern_C;149,3155 -typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3228 -typedef int should_see_this_array_type[should_see_this_array_type156,3310 +const A::B::T& abt 55,1766 +class A 56,1792 +class A { class B 56,1792 +class A { class B { int f(56,1792 +class A 57,1827 + int get_data(58,1837 + A operator+(59,1861 +is_muldiv_operation(61,1888 +domain foo 68,1956 + void f(69,1969 +void A::A(A72,1990 +struct A 73,2005 +struct A { A(73,2005 +struct B 74,2023 +struct B { B(74,2023 +void B::B(B75,2042 +void BE_Node::BE_Node(BE_Node76,2057 +class BE_Node 77,2084 +struct foo 79,2103 +class test 86,2157 + int f(87,2170 + int ff(89,2232 + int g(90,2255 +class AST_Root 92,2279 +class AST_Root;96,2328 +AST_ConcreteType::AST_ConcreteType(99,2394 +AST_Array::AST_Array(107,2533 + void f(115,2734 +struct A 117,2754 + ~A(118,2765 +A::~A(~A120,2778 +struct B 122,2790 + ~B(123,2801 +enum {dog,dog126,2818 +enum {dog, cat}cat126,2818 +enum {dog, cat} animals;126,2818 +struct {int teats;} cow;127,2843 +class Boo 129,2869 + enum {dog,dog130,2881 + enum {dog, cat}cat130,2881 + foo(133,2955 + Boo(137,2996 + Boo(138,3053 +Boo::Boo(141,3071 +typedef int should_see_this_one_enclosed_in_extern_C;149,3156 +typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3229 +typedef int should_see_this_array_type[should_see_this_array_type156,3311 cp-src/burton.cpp,124 ::dummy::dummy test::dummy1(dummy11,0 @@ -2845,15 +2858,15 @@ Comunicati e iniziative32,976 Ultime notizie dall'associazione63,2030 html-src/algrthms.html,467 -Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,271 -Descriptionalgorithms10,472 -Generating the Datagenalgorithm48,1948 -Convolutionallyconalgorithm55,2458 -Nextstatetable262,11326 -Outputoutputtable350,13566 -Mapping the Channel Symbolsmapping433,15781 -Adding Noise to theaddnoise439,16169 -Quantizing the Receivedquantizing469,18632 +Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,277 +Descriptionalgorithms10,481 +Generating the Datagenalgorithm48,1995 +Convolutionallyconalgorithm55,2512 +Nextstatetable262,11587 +Outputoutputtable350,13915 +Mapping the Channel Symbolsmapping433,16213 +Adding Noise to theaddnoise439,16607 +Quantizing the Receivedquantizing469,19100 html-src/software.html,439 Francesco 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 int tab_delete_first(91,1638 int tab_count_words(103,1820 +c-src/dostorture.c,198 +(*tag1 tag118,468 +#define notag2 26,577 +(*tag2 tag229,657 +(*tag3 tag339,809 +#define notag4 45,904 +(*tag4 tag448,1001 +tag5 57,1136 +tag6 66,1272 +int pp1(74,1389 +pp287,1504 +pp3(100,1616 + c-src/emacs/src/gmalloc.c,4207 #define USE_PTHREAD25,1002 #undef get_current_dir_name33,1126 @@ -2186,54 +2199,54 @@ class AU 53,1716 class AU { T x;53,1716 class B<B54,1735 class B { void f(54,1735 -const A::B::T& abt 55,1765 -class A 56,1791 -class A { class B 56,1791 -class A 57,1826 - A operator+(59,1860 -is_muldiv_operation(61,1887 -domain foo 68,1955 - void f(69,1968 -void A::A(A72,1989 -struct A 73,2004 -struct B 74,2022 -void B::B(B75,2041 -void BE_Node::BE_Node(BE_Node76,2056 -class BE_Node 77,2083 -struct foo 79,2102 - int x;80,2115 -class test 86,2156 - int f(87,2169 - int ff(89,2231 - int g(90,2254 -class AST_Root 92,2278 -AST_ConcreteType::AST_ConcreteType(99,2393 -AST_Array::AST_Array(107,2532 - void f(115,2733 -struct A 117,2753 -A::~A(~A120,2777 -struct B 122,2789 - ~B(123,2800 -enum {dog,dog126,2817 -enum {dog, cat}cat126,2817 -enum {dog, cat} animals;126,2817 -struct {int teats;127,2842 -struct {int teats;} cow;127,2842 -class Boo 129,2868 - enum {dog,dog130,2880 - enum {dog, cat}cat130,2880 - enum {dog, cat} animals;130,2880 - struct {int treats;131,2909 - struct {int treats;} cow;131,2909 - int i,132,2939 - int i,a,132,2939 - int i,a,b;132,2939 - foo(133,2954 - Boo(137,2995 -Boo::Boo(141,3070 -typedef int should_see_this_one_enclosed_in_extern_C;149,3155 -typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3228 -typedef int should_see_this_array_type[should_see_this_array_type156,3310 +const A::B::T& abt 55,1766 +class A 56,1792 +class A { class B 56,1792 +class A 57,1827 + A operator+(59,1861 +is_muldiv_operation(61,1888 +domain foo 68,1956 + void f(69,1969 +void A::A(A72,1990 +struct A 73,2005 +struct B 74,2023 +void B::B(B75,2042 +void BE_Node::BE_Node(BE_Node76,2057 +class BE_Node 77,2084 +struct foo 79,2103 + int x;80,2116 +class test 86,2157 + int f(87,2170 + int ff(89,2232 + int g(90,2255 +class AST_Root 92,2279 +AST_ConcreteType::AST_ConcreteType(99,2394 +AST_Array::AST_Array(107,2533 + void f(115,2734 +struct A 117,2754 +A::~A(~A120,2778 +struct B 122,2790 + ~B(123,2801 +enum {dog,dog126,2818 +enum {dog, cat}cat126,2818 +enum {dog, cat} animals;126,2818 +struct {int teats;127,2843 +struct {int teats;} cow;127,2843 +class Boo 129,2869 + enum {dog,dog130,2881 + enum {dog, cat}cat130,2881 + enum {dog, cat} animals;130,2881 + struct {int treats;131,2910 + struct {int treats;} cow;131,2910 + int i,132,2940 + int i,a,132,2940 + int i,a,b;132,2940 + foo(133,2955 + Boo(137,2996 +Boo::Boo(141,3071 +typedef int should_see_this_one_enclosed_in_extern_C;149,3156 +typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3229 +typedef int should_see_this_array_type[should_see_this_array_type156,3311 cp-src/burton.cpp,124 ::dummy::dummy test::dummy1(dummy11,0 @@ -2595,15 +2608,15 @@ Comunicati e iniziative32,976 Ultime notizie dall'associazione63,2030 html-src/algrthms.html,467 -Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,271 -Descriptionalgorithms10,472 -Generating the Datagenalgorithm48,1948 -Convolutionallyconalgorithm55,2458 -Nextstatetable262,11326 -Outputoutputtable350,13566 -Mapping the Channel Symbolsmapping433,15781 -Adding Noise to theaddnoise439,16169 -Quantizing the Receivedquantizing469,18632 +Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,277 +Descriptionalgorithms10,481 +Generating the Datagenalgorithm48,1995 +Convolutionallyconalgorithm55,2512 +Nextstatetable262,11587 +Outputoutputtable350,13915 +Mapping the Channel Symbolsmapping433,16213 +Adding Noise to theaddnoise439,16607 +Quantizing the Receivedquantizing469,19100 html-src/software.html,439 Francesco 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 int tab_delete_first(91,1638 int tab_count_words(103,1820 +c-src/dostorture.c,198 +(*tag1 tag118,468 +#define notag2 26,577 +(*tag2 tag229,657 +(*tag3 tag339,809 +#define notag4 45,904 +(*tag4 tag448,1001 +tag5 57,1136 +tag6 66,1272 +int pp1(74,1389 +pp287,1504 +pp3(100,1616 + c-src/emacs/src/gmalloc.c,3539 #define USE_PTHREAD25,1002 #undef get_current_dir_name33,1126 @@ -2060,46 +2073,46 @@ template class AT 52,1668 class AU 53,1716 class B<B54,1735 class B { void f(54,1735 -const A::B::T& abt 55,1765 -class A 56,1791 -class A { class B 56,1791 -class A 57,1826 - A operator+(59,1860 -is_muldiv_operation(61,1887 -domain foo 68,1955 - void f(69,1968 -void A::A(A72,1989 -struct A 73,2004 -struct B 74,2022 -void B::B(B75,2041 -void BE_Node::BE_Node(BE_Node76,2056 -class BE_Node 77,2083 -struct foo 79,2102 -class test 86,2156 - int f(87,2169 - int ff(89,2231 - int g(90,2254 -class AST_Root 92,2278 -AST_ConcreteType::AST_ConcreteType(99,2393 -AST_Array::AST_Array(107,2532 - void f(115,2733 -struct A 117,2753 -A::~A(~A120,2777 -struct B 122,2789 - ~B(123,2800 -enum {dog,dog126,2817 -enum {dog, cat}cat126,2817 -enum {dog, cat} animals;126,2817 -struct {int teats;} cow;127,2842 -class Boo 129,2868 - enum {dog,dog130,2880 - enum {dog, cat}cat130,2880 - foo(133,2954 - Boo(137,2995 -Boo::Boo(141,3070 -typedef int should_see_this_one_enclosed_in_extern_C;149,3155 -typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3228 -typedef int should_see_this_array_type[should_see_this_array_type156,3310 +const A::B::T& abt 55,1766 +class A 56,1792 +class A { class B 56,1792 +class A 57,1827 + A operator+(59,1861 +is_muldiv_operation(61,1888 +domain foo 68,1956 + void f(69,1969 +void A::A(A72,1990 +struct A 73,2005 +struct B 74,2023 +void B::B(B75,2042 +void BE_Node::BE_Node(BE_Node76,2057 +class BE_Node 77,2084 +struct foo 79,2103 +class test 86,2157 + int f(87,2170 + int ff(89,2232 + int g(90,2255 +class AST_Root 92,2279 +AST_ConcreteType::AST_ConcreteType(99,2394 +AST_Array::AST_Array(107,2533 + void f(115,2734 +struct A 117,2754 +A::~A(~A120,2778 +struct B 122,2790 + ~B(123,2801 +enum {dog,dog126,2818 +enum {dog, cat}cat126,2818 +enum {dog, cat} animals;126,2818 +struct {int teats;} cow;127,2843 +class Boo 129,2869 + enum {dog,dog130,2881 + enum {dog, cat}cat130,2881 + foo(133,2955 + Boo(137,2996 +Boo::Boo(141,3071 +typedef int should_see_this_one_enclosed_in_extern_C;149,3156 +typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3229 +typedef int should_see_this_array_type[should_see_this_array_type156,3311 cp-src/burton.cpp,124 ::dummy::dummy test::dummy1(dummy11,0 @@ -2442,15 +2455,15 @@ Comunicati e iniziative32,976 Ultime notizie dall'associazione63,2030 html-src/algrthms.html,467 -Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,271 -Descriptionalgorithms10,472 -Generating the Datagenalgorithm48,1948 -Convolutionallyconalgorithm55,2458 -Nextstatetable262,11326 -Outputoutputtable350,13566 -Mapping the Channel Symbolsmapping433,15781 -Adding Noise to theaddnoise439,16169 -Quantizing the Receivedquantizing469,18632 +Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,277 +Descriptionalgorithms10,481 +Generating the Datagenalgorithm48,1995 +Convolutionallyconalgorithm55,2512 +Nextstatetable262,11587 +Outputoutputtable350,13915 +Mapping the Channel Symbolsmapping433,16213 +Adding Noise to theaddnoise439,16607 +Quantizing the Receivedquantizing469,19100 html-src/software.html,439 Francesco 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 int tab_delete_first(91,1638 int tab_count_words(103,1820 +c-src/dostorture.c,198 +(*tag1 tag118,468 +#define notag2 26,577 +(*tag2 tag229,657 +(*tag3 tag339,809 +#define notag4 45,904 +(*tag4 tag448,1001 +tag5 57,1136 +tag6 66,1272 +int pp1(74,1389 +pp287,1504 +pp3(100,1616 + c-src/emacs/src/gmalloc.c,7311 #define USE_PTHREAD25,1002 #undef get_current_dir_name33,1126 @@ -2856,61 +2869,61 @@ class AU 53,1716 class AU { T x;53,1716 class B<B54,1735 class B { void f(54,1735 -const A::B::T& abt 55,1765 -class A 56,1791 -class A { class B 56,1791 -class A { class B { int f(56,1791 -class A 57,1826 - int get_data(58,1836 - A operator+(59,1860 -is_muldiv_operation(61,1887 -domain foo 68,1955 - void f(69,1968 -void A::A(A72,1989 -struct A 73,2004 -struct A { A(73,2004 -struct B 74,2022 -struct B { B(74,2022 -void B::B(B75,2041 -void BE_Node::BE_Node(BE_Node76,2056 -class BE_Node 77,2083 -struct foo 79,2102 - int x;80,2115 -class test 86,2156 - int f(87,2169 - int ff(89,2231 - int g(90,2254 -class AST_Root 92,2278 -class AST_Root;96,2327 -AST_ConcreteType::AST_ConcreteType(99,2393 -AST_Array::AST_Array(107,2532 - void f(115,2733 -struct A 117,2753 - ~A(118,2764 -A::~A(~A120,2777 -struct B 122,2789 - ~B(123,2800 -enum {dog,dog126,2817 -enum {dog, cat}cat126,2817 -enum {dog, cat} animals;126,2817 -struct {int teats;127,2842 -struct {int teats;} cow;127,2842 -class Boo 129,2868 - enum {dog,dog130,2880 - enum {dog, cat}cat130,2880 - enum {dog, cat} animals;130,2880 - struct {int treats;131,2909 - struct {int treats;} cow;131,2909 - int i,132,2939 - int i,a,132,2939 - int i,a,b;132,2939 - foo(133,2954 - Boo(137,2995 - Boo(138,3052 -Boo::Boo(141,3070 -typedef int should_see_this_one_enclosed_in_extern_C;149,3155 -typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3228 -typedef int should_see_this_array_type[should_see_this_array_type156,3310 +const A::B::T& abt 55,1766 +class A 56,1792 +class A { class B 56,1792 +class A { class B { int f(56,1792 +class A 57,1827 + int get_data(58,1837 + A operator+(59,1861 +is_muldiv_operation(61,1888 +domain foo 68,1956 + void f(69,1969 +void A::A(A72,1990 +struct A 73,2005 +struct A { A(73,2005 +struct B 74,2023 +struct B { B(74,2023 +void B::B(B75,2042 +void BE_Node::BE_Node(BE_Node76,2057 +class BE_Node 77,2084 +struct foo 79,2103 + int x;80,2116 +class test 86,2157 + int f(87,2170 + int ff(89,2232 + int g(90,2255 +class AST_Root 92,2279 +class AST_Root;96,2328 +AST_ConcreteType::AST_ConcreteType(99,2394 +AST_Array::AST_Array(107,2533 + void f(115,2734 +struct A 117,2754 + ~A(118,2765 +A::~A(~A120,2778 +struct B 122,2790 + ~B(123,2801 +enum {dog,dog126,2818 +enum {dog, cat}cat126,2818 +enum {dog, cat} animals;126,2818 +struct {int teats;127,2843 +struct {int teats;} cow;127,2843 +class Boo 129,2869 + enum {dog,dog130,2881 + enum {dog, cat}cat130,2881 + enum {dog, cat} animals;130,2881 + struct {int treats;131,2910 + struct {int treats;} cow;131,2910 + int i,132,2940 + int i,a,132,2940 + int i,a,b;132,2940 + foo(133,2955 + Boo(137,2996 + Boo(138,3053 +Boo::Boo(141,3071 +typedef int should_see_this_one_enclosed_in_extern_C;149,3156 +typedef int (*should_see_this_function_pointer)should_see_this_function_pointer153,3229 +typedef int should_see_this_array_type[should_see_this_array_type156,3311 cp-src/burton.cpp,124 ::dummy::dummy test::dummy1(dummy11,0 @@ -3326,15 +3339,15 @@ Comunicati e iniziative32,976 Ultime notizie dall'associazione63,2030 html-src/algrthms.html,467 -Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,271 -Descriptionalgorithms10,472 -Generating the Datagenalgorithm48,1948 -Convolutionallyconalgorithm55,2458 -Nextstatetable262,11326 -Outputoutputtable350,13566 -Mapping the Channel Symbolsmapping433,15781 -Adding Noise to theaddnoise439,16169 -Quantizing the Receivedquantizing469,18632 +Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms7,277 +Descriptionalgorithms10,481 +Generating the Datagenalgorithm48,1995 +Convolutionallyconalgorithm55,2512 +Nextstatetable262,11587 +Outputoutputtable350,13915 +Mapping the Channel Symbolsmapping433,16213 +Adding Noise to theaddnoise439,16607 +Quantizing the Receivedquantizing469,19100 html-src/software.html,439 Francesco 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 @@ ADASRC=$(addprefix ./ada-src/,etags-test-for.ada 2ataspri.adb 2ataspri.ads waroquiers.ada) ASRC=$(addprefix ./a-src/,empty.zz empty.zz.gz) CSRC=$(addprefix ./c-src/,abbrev.c .//c.c torture.c getopt.h etags.c\ - exit.c exit.strange_suffix sysdep.h tab.c\ + exit.c exit.strange_suffix sysdep.h tab.c dostorture.c\ emacs/src/gmalloc.c emacs/src/regex.h emacs/src/keyboard.c emacs/src/lisp.h\ machsyscalls.c machsyscalls.h fail.c a/b/b.c) ../etags/c-src/h.h CPSRC=$(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 @@ +/* Date: Thu, 05 Aug 1993 20:28:03 +0200 + From: "Tom R.Hageman" + Subject: more etags torture;-) [etags 7.3 patch#3] + To: pot@CNUCE.CNR.IT + + Hi, + + This test file illustrates some more problems with etags (7.3): + + + 1. parentheses are confusing, + 2. preprocessor directives can disrupt other state machines. */ + +/* A small torture test for etags. */ + +/* The classic parenthesis nightmare, based on signal(). */ +void +(*tag1 (sig, handler)) () + int sig; + void (*handler) (); +{ + (*handler)(sig); + return handler; +} + +#define notag2 void +/* The classic, with user-defined return type. */ +notag2 +(*tag2 (sig, handler)) () + int sig; + void (*handler) (); +{ + (*handler)(sig); + return handler; +} + +/* The classic, in ANSI C style. */ +void +(*tag3 (int sig, void (*handler) (int))) (int) +{ + (*handler)(sig); + return handler; +} + +#define notag4 void +/* The classic, with user-defined return type, in ANSI C style. */ +notag4 +(*tag4 (int sig, void (*handler) (int))) (int) +{ + (*handler)(sig); + return handler; +} + + +/* A less tortuous example. */ +void +tag5 (handler, arg) +void (*handler)(); +void *arg; +{ + (*handler)(arg); +} + +/* A less tortuous example, in ANSI C style. */ +void +tag6 (void (*handler) (void *), void *arg) +{ + (*handler)(arg); +} + + +/* Interfering preprocessing torture */ + +int pp1( +#if (__STDC__) + int +#endif + bar) +#if (!__STDC__) + int bar; +#endif +{ + return bar; +} + +int +pp2 +#if __STDC__ + (int bar) +#else + (bar) + int bar; +#endif +{ + return bar; +} + +int +#if __STDC__ +pp3(int bar) +#else +pp3(bar) + int bar; +#endif +{ + return bar; +} 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::f(A* x) {} A > A,int>::f(A* x) {} template class AT { C t[n]; }; class AU { T x; }; -class B { void f() {} }; +class B { void f() {} }; const A::B::T& abt = abc; class A { class B { int f(); }; }; class 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 @@ - - - - - - - Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms - - -Description -of the Algorithms  (Part 1) -

 The steps involved in simulating a communication channel using -convolutional encoding and Viterbi decoding are as follows: -

    -
  • -Generate the data to be transmitted through -the channel-result is binary data bits
    • - -
  • -Convolutionally encode the data-result is channel -symbols
    • - -
  • -Map the one/zero channel symbols onto an antipodal -baseband signal, producing transmitted channel symbols
    • - -
  • -Add noise to the transmitted channel symbols-result -is received channel symbols
    • - -
  • -Quantize the received channel levels-one bit -quantization is called hard-decision, and two to n bit quantization is -called soft-decision (n is usually three or four)
    • - -
  • -Perform Viterbi decoding on the quantized -received channel symbols-result is again binary data bits
    • - -
  • -Compare the decoded data bits to the transmitted data bits and count the -number of errors.
    • -
-Many of you will notice that I left out the steps of modulating the -channel symbols onto a transmitted carrier, and then demodulating the received -carrier to recover the channel symbols. You're right, but we can accurately -model the effects of AWGN even though we bypass those steps. -

Generating the Data -

Generating the data to be transmitted through the channel can be accomplished -quite simply by using a random number generator. One that produces a uniform -distribution of numbers on the interval 0 to a maximum value is provided -in C: rand (). Using this function, we can say that any value -less than half of the maximum value is a zero; any value greater than or -equal to half of the maximum value is a one. -

Convolutionally -Encoding the Data -

Convolutionally encoding the data is accomplished using a shift register -and associated combinatorial logic that performs modulo-two addition. (A -shift register is merely a chain of flip-flops wherein the output of the -nth flip-flop is tied to the input of the (n+1)th flip-flop. Every time -the active edge of the clock occurs, the input to the flip-flop is clocked -through to the output, and thus the data are shifted over one stage.) The -combinatorial logic is often in the form of cascaded exclusive-or gates. -As a reminder, exclusive-or gates are two-input, one-output gates often -represented by the logic symbol shown below, -

-

exclusive-or gate symbol

- -

that implement the following truth-table: -
  -
  -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
-
Input A
-		 -
Input B
-		 -
Output -

(A xor B)

-
-
0
-		 -
0
-		 -
0
-
-
0
-		 -
1
-		 -
1
-
-
1
-		 -
0
-		 -
1
-
-
1
-		 -
1
-		 -
0
-
- -

The exclusive-or gate performs modulo-two addition of its inputs. When -you cascade q two-input exclusive-or gates, with the output of the first -one feeding one of the inputs of the second one, the output of the second -one feeding one of the inputs of the third one, etc., the output of the -last one in the chain is the modulo-two sum of the q + 1 inputs. -

Another way to illustrate the modulo-two adder, and the way that is -most commonly used in textbooks, is as a circle with a + symbol inside, -thus: -

-

modulo-two adder symbol

- -

Now that we have the two basic components of the convolutional encoder -(flip-flops comprising the shift register and exclusive-or gates comprising -the associated modulo-two adders) defined, let's look at a picture of a -convolutional encoder for a rate 1/2, K = 3, m = 2 code: -
  -
  -
-

-

rate 1/2 K = 3 (7, 5) convolutional encoder

- -

In this encoder, data bits are provided at a rate of k bits per second. -Channel symbols are output at a rate of n = 2k symbols per second. The -input bit is stable during the encoder cycle. The encoder cycle starts -when an input clock edge occurs. When the input clock edge occurs, the -output of the left-hand flip-flop is clocked into the right-hand flip-flop, -the previous input bit is clocked into the left-hand flip-flop, and a new -input bit becomes available. Then the outputs of the upper and lower modulo-two -adders become stable. The output selector (SEL A/B block) cycles through -two states-in the first state, it selects and outputs the output of the -upper modulo-two adder; in the second state, it selects and outputs the -output of the lower modulo-two adder. -

The encoder shown above encodes the K = 3, (7, 5) convolutional code. -The octal numbers 7 and 5 represent the code generator polynomials, which -when read in binary (1112 and 1012) correspond to -the shift register connections to the upper and lower modulo-two adders, -respectively. This code has been determined to be the "best" code for rate -1/2, K = 3. It is the code I will use for the remaining discussion and -examples, for reasons that will become readily apparent when we get into -the Viterbi decoder algorithm. -

Let's look at an example input data stream, and the corresponding output -data stream: -

Let the input sequence be 0101110010100012. -

Assume that the outputs of both of the flip-flops in the shift register -are initially cleared, i.e. their outputs are zeroes. The first clock cycle -makes the first input bit, a zero, available to the encoder. The flip-flop -outputs are both zeroes. The inputs to the modulo-two adders are all zeroes, -so the output of the encoder is 002. -

The second clock cycle makes the second input bit available to the encoder. -The left-hand flip-flop clocks in the previous bit, which was a zero, and -the right-hand flip-flop clocks in the zero output by the left-hand flip-flop. -The inputs to the top modulo-two adder are 1002, so the output -is a one. The inputs to the bottom modulo-two adder are 102, -so the output is also a one. So the encoder outputs 112 for -the channel symbols. -

The third clock cycle makes the third input bit, a zero, available to -the encoder. The left-hand flip-flop clocks in the previous bit, which -was a one, and the right-hand flip-flop clocks in the zero from two bit-times -ago. The inputs to the top modulo-two adder are 0102, so the -output is a one. The inputs to the bottom modulo-two adder are 002, -so the output is zero. So the encoder outputs 102 for the channel -symbols. -

And so on. The timing diagram shown below illustrates the process: -
  -
  -
-

-

timing diagram for rate 1/2 convolutional encoder

- -


-
-
-

After all of the inputs have been presented to the encoder, the output -sequence will be: -

00 11 10 00 01 10 01 11 11 10 00 10 11 00 112. -

Notice that I have paired the encoder outputs-the first bit in each -pair is the output of the upper modulo-two adder; the second bit in each -pair is the output of the lower modulo-two adder. -

You can see from the structure of the rate 1/2 K = 3 convolutional encoder -and from the example given above that each input bit has an effect on three -successive pairs of output symbols. That is an extremely important point -and that is what gives the convolutional code its error-correcting power. -The reason why will become evident when we get into the Viterbi decoder -algorithm. -

Now if we are only going to send the 15 data bits given above, in order -for the last bit to affect three pairs of output symbols, we need to output -two more pairs of symbols. This is accomplished in our example encoder -by clocking the convolutional encoder flip-flops two ( = m) more times, -while holding the input at zero. This is called "flushing" the encoder, -and results in two more pairs of output symbols. The final binary output -of the encoder is thus 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11 10 -112. If we don't perform the flushing operation, the last m -bits of the message have less error-correction capability than the first -through (m - 1)th bits had. This is a pretty important thing to remember -if you're going to use this FEC technique in a burst-mode environment. -So's the step of clearing the shift register at the beginning of each burst. -The encoder must start in a known state and end in a known state for the -decoder to be able to reconstruct the input data sequence properly. -

Now, let's look at the encoder from another perspective. You can think -of the encoder as a simple state machine. The example encoder has two bits -of memory, so there are four possible states. Let's give the left-hand -flip-flop a binary weight of 21, and the right-hand flip-flop -a binary weight of 20. Initially, the encoder is in the all-zeroes -state. If the first input bit is a zero, the encoder stays in the all zeroes -state at the next clock edge. But if the input bit is a one, the encoder -transitions to the 102 state at the next clock edge. Then, if -the next input bit is zero, the encoder transitions to the 012 -state, otherwise, it transitions to the 112 state. The following -table gives the next state given the current state and the input, with -the states given in binary: -
  -
  -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  -
Next -State, if 
-
-
Current State
-		 -
Input = 0:
-		 -
Input = 1:
-
-
00
-		 -
00
-		 -
10
-
-
01
-		 -
00
-		 -
10
-
-
10
-		 -
01
-		 -
11
-
-
11
-		 -
01
-		 -
11
-
- -
  -

The above table is often called a state transition table. We'll refer -to it as the next state table. Now let us look at a table -that lists the channel output symbols, given the current state and the -input data, which we'll refer to as the output table: -
  -
  -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
-
Output -Symbols, if
-
-
Current State
-		 -
Input = 0:
-		 -
Input = 1:
-
-
00
-		 -
00
-		 -
11
-
-
01
-		 -
11
-		 -
00
-
-
10
-		 -
10
-		 -
01
-
-
11
-		 -
01
-		 -
10
-
- -
  -

You should now see that with these two tables, you can completely describe -the behavior of the example rate 1/2, K = 3 convolutional encoder. Note -that both of these tables have 2(K - 1) rows, and 2k -columns, where K is the constraint length and k is the number of bits input -to the encoder for each cycle. These two tables will come in handy when -we start discussing the Viterbi decoder algorithm. -

Mapping the Channel Symbols -to Signal Levels -

Mapping the one/zero output of the convolutional encoder onto an antipodal -baseband signaling scheme is simply a matter of translating zeroes to +1s -and ones to -1s. This can be accomplished by performing the operation y -= 1 - 2x on each convolutional encoder output symbol. -

Adding Noise to the -Transmitted Symbols -

Adding noise to the transmitted channel symbols produced by the convolutional -encoder involves generating Gaussian random numbers, scaling the numbers -according to the desired energy per symbol to noise density ratio, Es/N0, -and adding the scaled Gaussian random numbers to the channel symbol values. -

For the uncoded channel, Es/N0 = Eb/N0, -since there is one channel symbol per bit.  However, for the coded -channel, Es/N0 = Eb/N0 + 10log10(k/n).  -For example, for rate 1/2 coding, Es/N0 = Eb/N0 -+ 10log10(1/2) = Eb/N0 - 3.01 dB.  -Similarly, for rate 2/3 coding, Es/N0 = Eb/N0 -+ 10log10(2/3) = Eb/N0 - 1.76 dB. -

The Gaussian random number generator is the only interesting part of -this task. C only provides a uniform random number generator, rand(). -In order to obtain Gaussian random numbers, we take advantage of relationships -between uniform, Rayleigh, and Gaussian distributions: -

Given a uniform random variable U, a Rayleigh random variable R can -be obtained by: -

equation for Rayleigh random deviate given uniform random deviate -

where is -the variance of the Rayleigh random variable, and given R and a second -uniform random variable V, two Gaussian random variables G and H can be -obtained by -

G = R cos U and H = R sin V. -

In the AWGN channel, the signal is corrupted by additive noise, n(t), -which has the power spectrum No/2 watts/Hz. The variance varianceof -this noise is equal to noise density div by two. -If we set the energy per symbol Es equal to 1, then equation relating variance to SNR. -So equation for AWGN st dev given SNR. -

Quantizing the Received -Channel Symbols -

An ideal Viterbi decoder would work with infinite precision, or at least -with floating-point numbers. In practical systems, we quantize the received -channel symbols with one or a few bits of precision in order to reduce -the complexity of the Viterbi decoder, not to mention the circuits that -precede it. If the received channel symbols are quantized to one-bit precision -(< 0V = 1, > 0V = 0), the result is called hard-decision data. -If the received channel symbols are quantized with more than one bit of -precision, the result is called soft-decision data. A Viterbi decoder with -soft decision data inputs quantized to three or four bits of precision -can perform about 2 dB better than one working with hard-decision inputs. -The usual quantization precision is three bits. More bits provide little -additional improvement. -

The selection of the quantizing levels is an important design decision -because it can have a significant effect on the performance of the link. -The following is a very brief explanation of one way to set those levels. -Let's assume our received signal levels in the absence of noise are -1V -= 1, +1V = 0. With noise, our received signal has mean +/- 1 and standard -deviation equation for AWGN st dev given SNR. -Let's use a uniform, three-bit quantizer having the input/output relationship -shown in the figure below, where D is a decision level that we will calculate -shortly: -

-

8-level quantizer function plot

- -

The decision level, D, can be calculated according to the formula equation for quantizer decision level, -where Es/N0 is the energy per symbol to noise density -ratio. (The above figure was redrawn from Figure 2 of Advanced Hardware -Architecture's ANRS07-0795, "Soft Decision Thresholds and Effects on Viterbi -Performance". See the bibliography  -for a link to their web pages.) -

Click here to proceed to the description -of the Viterbi decoding algorithm itself... -

Or click on one of the links below to go to the beginning of that section: -

 Introduction -
 Description of the Algorithms  -(Part 2) -
 Simulation Source Code Examples -
 Example Simulation Results -
 Bibliography -
 About Spectrum Applications... -
  -
  -
-
-

-

- - - + + + + + + + Tutorial on Convolutional Coding with Viterbi Decoding--Description of the Data Generation, Convolutional Encoding, Channel Mapping and AWGN, and Quantizing Algorithms + + +Description +of the Algorithms  (Part 1) +

 The steps involved in simulating a communication channel using +convolutional encoding and Viterbi decoding are as follows: +

    +
  • +Generate the data to be transmitted through +the channel-result is binary data bits
    • + +
  • +Convolutionally encode the data-result is channel +symbols
    • + +
  • +Map the one/zero channel symbols onto an antipodal +baseband signal, producing transmitted channel symbols
    • + +
  • +Add noise to the transmitted channel symbols-result +is received channel symbols
    • + +
  • +Quantize the received channel levels-one bit +quantization is called hard-decision, and two to n bit quantization is +called soft-decision (n is usually three or four)
    • + +
  • +Perform Viterbi decoding on the quantized +received channel symbols-result is again binary data bits
    • + +
  • +Compare the decoded data bits to the transmitted data bits and count the +number of errors.
    • +
+Many of you will notice that I left out the steps of modulating the +channel symbols onto a transmitted carrier, and then demodulating the received +carrier to recover the channel symbols. You're right, but we can accurately +model the effects of AWGN even though we bypass those steps. +

Generating the Data +

Generating the data to be transmitted through the channel can be accomplished +quite simply by using a random number generator. One that produces a uniform +distribution of numbers on the interval 0 to a maximum value is provided +in C: rand (). Using this function, we can say that any value +less than half of the maximum value is a zero; any value greater than or +equal to half of the maximum value is a one. +

Convolutionally +Encoding the Data +

Convolutionally encoding the data is accomplished using a shift register +and associated combinatorial logic that performs modulo-two addition. (A +shift register is merely a chain of flip-flops wherein the output of the +nth flip-flop is tied to the input of the (n+1)th flip-flop. Every time +the active edge of the clock occurs, the input to the flip-flop is clocked +through to the output, and thus the data are shifted over one stage.) The +combinatorial logic is often in the form of cascaded exclusive-or gates. +As a reminder, exclusive-or gates are two-input, one-output gates often +represented by the logic symbol shown below, +

+

exclusive-or gate symbol

+ +

that implement the following truth-table: +
  +
  +

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+
Input A
+		 +
Input B
+		 +
Output +

(A xor B)

+
+
0
+		 +
0
+		 +
0
+
+
0
+		 +
1
+		 +
1
+
+
1
+		 +
0
+		 +
1
+
+
1
+		 +
1
+		 +
0
+
+ +

The exclusive-or gate performs modulo-two addition of its inputs. When +you cascade q two-input exclusive-or gates, with the output of the first +one feeding one of the inputs of the second one, the output of the second +one feeding one of the inputs of the third one, etc., the output of the +last one in the chain is the modulo-two sum of the q + 1 inputs. +

Another way to illustrate the modulo-two adder, and the way that is +most commonly used in textbooks, is as a circle with a + symbol inside, +thus: +

+

modulo-two adder symbol

+ +

Now that we have the two basic components of the convolutional encoder +(flip-flops comprising the shift register and exclusive-or gates comprising +the associated modulo-two adders) defined, let's look at a picture of a +convolutional encoder for a rate 1/2, K = 3, m = 2 code: +
  +
  +
+

+

rate 1/2 K = 3 (7, 5) convolutional encoder

+ +

In this encoder, data bits are provided at a rate of k bits per second. +Channel symbols are output at a rate of n = 2k symbols per second. The +input bit is stable during the encoder cycle. The encoder cycle starts +when an input clock edge occurs. When the input clock edge occurs, the +output of the left-hand flip-flop is clocked into the right-hand flip-flop, +the previous input bit is clocked into the left-hand flip-flop, and a new +input bit becomes available. Then the outputs of the upper and lower modulo-two +adders become stable. The output selector (SEL A/B block) cycles through +two states-in the first state, it selects and outputs the output of the +upper modulo-two adder; in the second state, it selects and outputs the +output of the lower modulo-two adder. +

The encoder shown above encodes the K = 3, (7, 5) convolutional code. +The octal numbers 7 and 5 represent the code generator polynomials, which +when read in binary (1112 and 1012) correspond to +the shift register connections to the upper and lower modulo-two adders, +respectively. This code has been determined to be the "best" code for rate +1/2, K = 3. It is the code I will use for the remaining discussion and +examples, for reasons that will become readily apparent when we get into +the Viterbi decoder algorithm. +

Let's look at an example input data stream, and the corresponding output +data stream: +

Let the input sequence be 0101110010100012. +

Assume that the outputs of both of the flip-flops in the shift register +are initially cleared, i.e. their outputs are zeroes. The first clock cycle +makes the first input bit, a zero, available to the encoder. The flip-flop +outputs are both zeroes. The inputs to the modulo-two adders are all zeroes, +so the output of the encoder is 002. +

The second clock cycle makes the second input bit available to the encoder. +The left-hand flip-flop clocks in the previous bit, which was a zero, and +the right-hand flip-flop clocks in the zero output by the left-hand flip-flop. +The inputs to the top modulo-two adder are 1002, so the output +is a one. The inputs to the bottom modulo-two adder are 102, +so the output is also a one. So the encoder outputs 112 for +the channel symbols. +

The third clock cycle makes the third input bit, a zero, available to +the encoder. The left-hand flip-flop clocks in the previous bit, which +was a one, and the right-hand flip-flop clocks in the zero from two bit-times +ago. The inputs to the top modulo-two adder are 0102, so the +output is a one. The inputs to the bottom modulo-two adder are 002, +so the output is zero. So the encoder outputs 102 for the channel +symbols. +

And so on. The timing diagram shown below illustrates the process: +
  +
  +
+

+

timing diagram for rate 1/2 convolutional encoder

+ +


+
+
+

After all of the inputs have been presented to the encoder, the output +sequence will be: +

00 11 10 00 01 10 01 11 11 10 00 10 11 00 112. +

Notice that I have paired the encoder outputs-the first bit in each +pair is the output of the upper modulo-two adder; the second bit in each +pair is the output of the lower modulo-two adder. +

You can see from the structure of the rate 1/2 K = 3 convolutional encoder +and from the example given above that each input bit has an effect on three +successive pairs of output symbols. That is an extremely important point +and that is what gives the convolutional code its error-correcting power. +The reason why will become evident when we get into the Viterbi decoder +algorithm. +

Now if we are only going to send the 15 data bits given above, in order +for the last bit to affect three pairs of output symbols, we need to output +two more pairs of symbols. This is accomplished in our example encoder +by clocking the convolutional encoder flip-flops two ( = m) more times, +while holding the input at zero. This is called "flushing" the encoder, +and results in two more pairs of output symbols. The final binary output +of the encoder is thus 00 11 10 00 01 10 01 11 11 10 00 10 11 00 11 10 +112. If we don't perform the flushing operation, the last m +bits of the message have less error-correction capability than the first +through (m - 1)th bits had. This is a pretty important thing to remember +if you're going to use this FEC technique in a burst-mode environment. +So's the step of clearing the shift register at the beginning of each burst. +The encoder must start in a known state and end in a known state for the +decoder to be able to reconstruct the input data sequence properly. +

Now, let's look at the encoder from another perspective. You can think +of the encoder as a simple state machine. The example encoder has two bits +of memory, so there are four possible states. Let's give the left-hand +flip-flop a binary weight of 21, and the right-hand flip-flop +a binary weight of 20. Initially, the encoder is in the all-zeroes +state. If the first input bit is a zero, the encoder stays in the all zeroes +state at the next clock edge. But if the input bit is a one, the encoder +transitions to the 102 state at the next clock edge. Then, if +the next input bit is zero, the encoder transitions to the 012 +state, otherwise, it transitions to the 112 state. The following +table gives the next state given the current state and the input, with +the states given in binary: +
  +
  +

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
  +
Next +State, if 
+
+
Current State
+		 +
Input = 0:
+		 +
Input = 1:
+
+
00
+		 +
00
+		 +
10
+
+
01
+		 +
00
+		 +
10
+
+
10
+		 +
01
+		 +
11
+
+
11
+		 +
01
+		 +
11
+
+ +
  +

The above table is often called a state transition table. We'll refer +to it as the next state table. Now let us look at a table +that lists the channel output symbols, given the current state and the +input data, which we'll refer to as the output table: +
  +
  +

+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
+
Output +Symbols, if
+
+
Current State
+		 +
Input = 0:
+		 +
Input = 1:
+
+
00
+		 +
00
+		 +
11
+
+
01
+		 +
11
+		 +
00
+
+
10
+		 +
10
+		 +
01
+
+
11
+		 +
01
+		 +
10
+
+ +
  +

You should now see that with these two tables, you can completely describe +the behavior of the example rate 1/2, K = 3 convolutional encoder. Note +that both of these tables have 2(K - 1) rows, and 2k +columns, where K is the constraint length and k is the number of bits input +to the encoder for each cycle. These two tables will come in handy when +we start discussing the Viterbi decoder algorithm. +

Mapping the Channel Symbols +to Signal Levels +

Mapping the one/zero output of the convolutional encoder onto an antipodal +baseband signaling scheme is simply a matter of translating zeroes to +1s +and ones to -1s. This can be accomplished by performing the operation y += 1 - 2x on each convolutional encoder output symbol. +

Adding Noise to the +Transmitted Symbols +

Adding noise to the transmitted channel symbols produced by the convolutional +encoder involves generating Gaussian random numbers, scaling the numbers +according to the desired energy per symbol to noise density ratio, Es/N0, +and adding the scaled Gaussian random numbers to the channel symbol values. +

For the uncoded channel, Es/N0 = Eb/N0, +since there is one channel symbol per bit.  However, for the coded +channel, Es/N0 = Eb/N0 + 10log10(k/n).  +For example, for rate 1/2 coding, Es/N0 = Eb/N0 ++ 10log10(1/2) = Eb/N0 - 3.01 dB.  +Similarly, for rate 2/3 coding, Es/N0 = Eb/N0 ++ 10log10(2/3) = Eb/N0 - 1.76 dB. +

The Gaussian random number generator is the only interesting part of +this task. C only provides a uniform random number generator, rand(). +In order to obtain Gaussian random numbers, we take advantage of relationships +between uniform, Rayleigh, and Gaussian distributions: +

Given a uniform random variable U, a Rayleigh random variable R can +be obtained by: +

equation for Rayleigh random deviate given uniform random deviate +

where is +the variance of the Rayleigh random variable, and given R and a second +uniform random variable V, two Gaussian random variables G and H can be +obtained by +

G = R cos U and H = R sin V. +

In the AWGN channel, the signal is corrupted by additive noise, n(t), +which has the power spectrum No/2 watts/Hz. The variance varianceof +this noise is equal to noise density div by two. +If we set the energy per symbol Es equal to 1, then equation relating variance to SNR. +So equation for AWGN st dev given SNR. +

Quantizing the Received +Channel Symbols +

An ideal Viterbi decoder would work with infinite precision, or at least +with floating-point numbers. In practical systems, we quantize the received +channel symbols with one or a few bits of precision in order to reduce +the complexity of the Viterbi decoder, not to mention the circuits that +precede it. If the received channel symbols are quantized to one-bit precision +(< 0V = 1, > 0V = 0), the result is called hard-decision data. +If the received channel symbols are quantized with more than one bit of +precision, the result is called soft-decision data. A Viterbi decoder with +soft decision data inputs quantized to three or four bits of precision +can perform about 2 dB better than one working with hard-decision inputs. +The usual quantization precision is three bits. More bits provide little +additional improvement. +

The selection of the quantizing levels is an important design decision +because it can have a significant effect on the performance of the link. +The following is a very brief explanation of one way to set those levels. +Let's assume our received signal levels in the absence of noise are -1V += 1, +1V = 0. With noise, our received signal has mean +/- 1 and standard +deviation equation for AWGN st dev given SNR. +Let's use a uniform, three-bit quantizer having the input/output relationship +shown in the figure below, where D is a decision level that we will calculate +shortly: +

+

8-level quantizer function plot

+ +

The decision level, D, can be calculated according to the formula equation for quantizer decision level, +where Es/N0 is the energy per symbol to noise density +ratio. (The above figure was redrawn from Figure 2 of Advanced Hardware +Architecture's ANRS07-0795, "Soft Decision Thresholds and Effects on Viterbi +Performance". See the bibliography  +for a link to their web pages.) +

Click here to proceed to the description +of the Viterbi decoding algorithm itself... +

Or click on one of the links below to go to the beginning of that section: +

 Introduction +
 Description of the Algorithms  +(Part 2) +
 Simulation Source Code Examples +
 Example Simulation Results +
 Bibliography +
 About Spectrum Applications... +
  +
  +
+
+

+

+ + + -- 2.39.2