5 files changed, 395 insertions, 0 deletions
diff --git a/gr-digital/python/digital/utils/__init__.py b/gr-digital/python/digital/utils/__init__.py
new file mode 100644
index 0000000000..b3e997f9f8
--- /dev/null
+++ b/gr-digital/python/digital/utils/__init__.py
@@ -0,0 +1,21 @@
+#!/usr/bin/env python
+#
+# Copyright 2011 Free Software Foundation, Inc.
+# 
+# This file is part of GNU Radio
+# 
+# GNU Radio is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3, or (at your option)
+# any later version.
+# 
+# GNU Radio is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with GNU Radio; see the file COPYING.  If not, write to
+# the Free Software Foundation, Inc., 51 Franklin Street,
+# Boston, MA 02110-1301, USA.
+# 
diff --git a/gr-digital/python/digital/utils/alignment.py b/gr-digital/python/digital/utils/alignment.py
new file mode 100644
index 0000000000..f3ad3781e2
--- /dev/null
+++ b/gr-digital/python/digital/utils/alignment.py
@@ -0,0 +1,141 @@
+#!/usr/bin/env python
+#
+# Copyright 2011 Free Software Foundation, Inc.
+# 
+# This file is part of GNU Radio
+# 
+# GNU Radio is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3, or (at your option)
+# any later version.
+# 
+# GNU Radio is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with GNU Radio; see the file COPYING.  If not, write to
+# the Free Software Foundation, Inc., 51 Franklin Street,
+# Boston, MA 02110-1301, USA.
+# 
+"""
+This module contains functions for aligning sequences.
+
+>>> import random
+>>> rndm = random.Random()
+>>> rndm.seed(1234)
+>>> ran_seq = [rndm.randint(0,1) for i in range(0, 100)]
+>>> offset_seq = [0] * 20 + ran_seq
+>>> correct, overlap, offset = align_sequences(ran_seq, offset_seq)
+>>> print(correct, overlap, offset)
+(1.0, 100, -20)
+>>> offset_err_seq = []
+>>> for bit in offset_seq:
+...     if rndm.randint(0,4) == 4:
+...         offset_err_seq.append(rndm.randint(0,1))
+...     else:
+...         offset_err_seq.append(bit)
+>>> correct, overlap, offset = align_sequences(ran_seq, offset_err_seq)
+>>> print(overlap, offset)
+(100, -20)
+
+"""
+
+import random
+
+# DEFAULT PARAMETERS
+# If the fraction of matching bits between two sequences is greater than
+# this the sequences are assumed to be aligned.
+def_correct_cutoff = 0.9
+# The maximum offset to test during sequence alignment.
+def_max_offset = 500
+# The maximum number of samples to take from two sequences to check alignment.
+def_num_samples = 1000
+
+def compare_sequences(d1, d2, offset, sample_indices=None):
+    """
+    Takes two binary sequences and an offset and returns the number of
+    matching entries and the number of compared entries.
+    d1 & d2 -- sequences
+    offset -- offset of d2 relative to d1
+    sample_indices -- a list of indices to use for the comparison
+    """
+    max_index = min(len(d1), len(d2)+offset)
+    if sample_indices is None:
+        sample_indices = range(0, max_index)
+    correct = 0
+    total = 0
+    for i in sample_indices:
+        if i >= max_index:
+            break
+        if d1[i] == d2[i-offset]:
+            correct += 1
+        total += 1
+    return (correct, total)
+
+def random_sample(size, num_samples=def_num_samples, seed=None):
+    """
+    Returns a set of random integers between 0 and (size-1).
+    The set contains no more than num_samples integers.
+    """
+    rndm = random.Random()
+    rndm.seed(seed)
+    if num_samples > size:
+        indices = set(range(0, size))
+    else:
+        if num_samples > size/2:
+            num_samples = num_samples/2
+        indices = set([])
+        while len(indices) < num_samples:
+            index = rndm.randint(0, size-1)
+            indices.add(index)
+    indices = list(indices)
+    indices.sort()
+    return indices
+
+def align_sequences(d1, d2,
+                    num_samples=def_num_samples,
+                    max_offset=def_max_offset,
+                    correct_cutoff=def_correct_cutoff,
+                    seed=None,
+                    indices=None):
+    """
+    Takes two sequences and finds the offset and which the two sequences best
+    match.  It returns the fraction correct, the number of entries compared,
+    the offset.
+    d1 & d2 -- sequences to compare
+    num_samples -- the maximum number of entries to compare
+    max_offset -- the maximum offset between the sequences that is checked
+    correct_cutoff -- If the fraction of bits correct is greater than this then
+                      the offset is assumed to optimum.
+    seed -- a random number seed
+    indices -- an explicit list of the indices used to compare the two sequences
+    """
+    max_overlap = max(len(d1), len(d2))
+    if indices is None:
+        indices = random_sample(max_overlap, num_samples, seed)
+    max_frac_correct = 0
+    best_offset = None
+    best_compared = None
+    best_correct = None
+    pos_range = range(0, min(len(d1), max_offset))
+    neg_range = range(-1, -min(len(d2), max_offset), -1)
+    # Interleave the positive and negative offsets.
+    int_range = [item for items in zip(pos_range, neg_range) for item in items]
+    for offset in int_range:
+        correct, compared = compare_sequences(d1, d2, offset, indices)
+        frac_correct = 1.0*correct/compared
+        if frac_correct > max_frac_correct:
+            max_frac_correct = frac_correct
+            best_offset = offset
+            best_compared = compared
+            best_correct = correct
+            if frac_correct > correct_cutoff:
+                break
+    return max_frac_correct, best_compared, best_offset, indices
+    
+if __name__ == "__main__":
+    import doctest
+    doctest.testmod()
+    
diff --git a/gr-digital/python/digital/utils/gray_code.py b/gr-digital/python/digital/utils/gray_code.py
new file mode 100644
index 0000000000..926a1ded10
--- /dev/null
+++ b/gr-digital/python/digital/utils/gray_code.py
@@ -0,0 +1,66 @@
+#!/usr/bin/env python
+#
+# Copyright 2011 Free Software Foundation, Inc.
+# 
+# This file is part of GNU Radio
+# 
+# GNU Radio is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3, or (at your option)
+# any later version.
+# 
+# GNU Radio is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with GNU Radio; see the file COPYING.  If not, write to
+# the Free Software Foundation, Inc., 51 Franklin Street,
+# Boston, MA 02110-1301, USA.
+# 
+
+class GrayCodeGenerator(object):
+    """
+    Generates and caches gray codes.
+    """
+
+    def __init__(self):
+        self.gcs = [0, 1]
+        # The last power of two passed through.
+        self.lp2 = 2
+        # The next power of two that will be passed through.
+        self.np2 = 4
+        # Curent index
+        self.i = 2
+
+    def get_gray_code(self, length):
+        """
+        Returns a list of gray code of given length.
+        """
+        if len(self.gcs) < length:
+            self.generate_new_gray_code(length)
+        return self.gcs[:length]
+    
+    def generate_new_gray_code(self, length):
+        """
+        Generates new gray code and places into cache.
+        """
+        while len(self.gcs) < length:
+            if self.i == self.lp2:
+                # if i is a power of two then gray number is of form 1100000...
+                result = self.i + self.i/2
+            else:
+                # if not we take advantage of the symmetry of all but the last bit
+                # around a power of two.
+                result = self.gcs[2*self.lp2-1-self.i] + self.lp2
+            self.gcs.append(result)
+            self.i += 1
+            if self.i == self.np2:
+                self.lp2 = self.i
+                self.np2 = self.i*2
+
+_gray_code_generator = GrayCodeGenerator()
+
+gray_code = _gray_code_generator.get_gray_code
+
diff --git a/gr-digital/python/digital/utils/mod_codes.py b/gr-digital/python/digital/utils/mod_codes.py
new file mode 100644
index 0000000000..f55fe41b8b
--- /dev/null
+++ b/gr-digital/python/digital/utils/mod_codes.py
@@ -0,0 +1,34 @@
+#!/usr/bin/env python
+#
+# Copyright 2011 Free Software Foundation, Inc.
+# 
+# This file is part of GNU Radio
+# 
+# GNU Radio is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3, or (at your option)
+# any later version.
+# 
+# GNU Radio is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with GNU Radio; see the file COPYING.  If not, write to
+# the Free Software Foundation, Inc., 51 Franklin Street,
+# Boston, MA 02110-1301, USA.
+# 
+
+# Constants used to represent what coding to use.
+GRAY_CODE = 'gray'
+SET_PARTITION_CODE = 'set-partition'
+NO_CODE = 'none'
+
+codes = (GRAY_CODE, SET_PARTITION_CODE, NO_CODE)
+
+def invert_code(code):
+    c = enumerate(code)
+    ic = [(b, a) for (a, b) in c]
+    ic.sort()
+    return [a for (b, a) in ic]
diff --git a/gr-digital/python/digital/utils/tagged_streams.py b/gr-digital/python/digital/utils/tagged_streams.py
new file mode 100644
index 0000000000..c7edbf61eb
--- /dev/null
+++ b/gr-digital/python/digital/utils/tagged_streams.py
@@ -0,0 +1,133 @@
+#!/usr/bin/env python
+#
+# Copyright 2013 Free Software Foundation, Inc.
+# 
+# This file is part of GNU Radio
+# 
+# GNU Radio is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 3, or (at your option)
+# any later version.
+# 
+# GNU Radio is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with GNU Radio; see the file COPYING.  If not, write to
+# the Free Software Foundation, Inc., 51 Franklin Street,
+# Boston, MA 02110-1301, USA.
+# 
+
+from gnuradio import gr
+import pmt
+
+def make_lengthtags(lengths, offsets, tagname='length', vlen=1):
+    tags = []
+    assert(len(offsets) == len(lengths))
+    for offset, length in zip(offsets, lengths):
+        tag = gr.tag_t()
+        tag.offset = offset/vlen
+        tag.key = pmt.string_to_symbol(tagname)
+        tag.value = pmt.from_long(length/vlen)
+        tags.append(tag)
+    return tags
+
+def string_to_vector(string):
+    v = []
+    for s in string:
+        v.append(ord(s))
+    return v
+
+def strings_to_vectors(strings, lengthtagname):
+    vs = [string_to_vector(string) for string in strings]
+    return packets_to_vectors(vs, lengthtagname)
+
+def vector_to_string(v):
+    s = []
+    for d in v:
+        s.append(chr(d))
+    return ''.join(s)
+
+def vectors_to_strings(data, tags, lengthtagname):
+    packets = vectors_to_packets(data, tags, lengthtagname)
+    return [vector_to_string(packet) for packet in packets]
+
+def count_bursts(data, tags, lengthtagname, vlen=1):
+    lengthtags = [t for t in tags
+                  if pmt.symbol_to_string(t.key) == lengthtagname]
+    lengths = {}
+    for tag in lengthtags:
+        if tag.offset in lengths:
+            raise ValueError(
+                "More than one tags with key {0} with the same offset={1}."
+                .format(lengthtagname, tag.offset))
+        lengths[tag.offset] = pmt.to_long(tag.value)*vlen
+    in_burst = False
+    in_packet = False
+    packet_length = None
+    packet_pos = None
+    burst_count = 0
+    for pos in range(len(data)):
+        if pos in lengths:
+            if in_packet:
+                print("Got tag at pos {0} current packet_pos is {1}".format(pos, packet_pos))
+                raise StandardError("Received packet tag while in packet.")
+            packet_pos = -1
+            packet_length = lengths[pos]
+            in_packet = True
+            if not in_burst:
+                burst_count += 1
+            in_burst = True
+        elif not in_packet:
+            in_burst = False
+        if in_packet:
+            packet_pos += 1
+            if packet_pos == packet_length-1:
+                in_packet = False
+                packet_pos = None
+    return burst_count
+
+def vectors_to_packets(data, tags, lengthtagname, vlen=1):
+    lengthtags = [t for t in tags
+                  if pmt.symbol_to_string(t.key) == lengthtagname]
+    lengths = {}
+    for tag in lengthtags:
+        if tag.offset in lengths:
+            raise ValueError(
+                "More than one tags with key {0} with the same offset={1}."
+                .format(lengthtagname, tag.offset))
+        lengths[tag.offset] = pmt.to_long(tag.value)*vlen
+    if 0 not in lengths:
+        raise ValueError("There is no tag with key {0} and an offset of 0"
+                         .format(lengthtagname))
+    pos = 0
+    packets = []
+    while pos < len(data):
+        if pos not in lengths:
+            raise ValueError("There is no tag with key {0} and an offset of {1}."
+                             "We were expecting one."
+                             .format(lengthtagname, pos))
+        length = lengths[pos]
+        if length == 0:
+            raise ValueError("Packets cannot have zero length.")
+        if pos+length > len(data):
+            raise ValueError("The final packet is incomplete.")
+        packets.append(data[pos: pos+length])
+        pos += length
+    return packets
+
+def packets_to_vectors(packets, lengthtagname, vlen=1):
+    tags = []
+    data = []
+    offset = 0
+    for packet in packets:
+        data.extend(packet)
+        tag = gr.tag_t()
+        tag.offset = offset/vlen
+        tag.key = pmt.string_to_symbol(lengthtagname)
+        tag.value = pmt.from_long(len(packet)/vlen)
+        tags.append(tag)
+        offset = offset + len(packet)
+    return data, tags