FilesExpand file tree

 master

/

decoder.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

104 lines (71 loc) · 3.86 KB

 master

/

decoder.py

Copy path

Top

File metadata and controls

• Code
• Blame

104 lines (71 loc) · 3.86 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

from core import *

def recover_graph(symbols, blocks_quantity):

""" Get back the same random indexes (or neighbors), thanks to the symbol id as seed.

For an easy implementation purpose, we register the indexes as property of the Symbols objects.

"""

for symbol in symbols:

neighbors, deg = generate_indexes(symbol.index, symbol.degree, blocks_quantity)

symbol.neighbors = {x for x in neighbors}

symbol.degree = deg

if VERBOSE:

symbol.log(blocks_quantity)

return symbols

def reduce_neighbors(block_index, blocks, symbols):

""" Loop over the remaining symbols to find for a common link between

each symbol and the last solved block `block`

To avoid increasing complexity and another for loop, the neighbors are stored as dictionnary

which enable to directly delete the entry after XORing back.

"""

for other_symbol in symbols:

if other_symbol.degree > 1 and block_index in other_symbol.neighbors:

# XOR the data and remove the index from the neighbors

other_symbol.data = np.bitwise_xor(blocks[block_index], other_symbol.data)

other_symbol.neighbors.remove(block_index)

other_symbol.degree -= 1

if VERBOSE:

print("XOR block_{} with symbol_{} :".format(block_index, other_symbol.index), list(other_symbol.neighbors.keys()))

def decode(symbols, blocks_quantity):

""" Iterative decoding - Decodes all the passed symbols to build back the data as blocks.

The function returns the data at the end of the process.

1. Search for an output symbol of degree one

(a) If such an output symbol y exists move to step 2.

(b) If no output symbols of degree one exist, iterative decoding exits and decoding fails.

2. Output symbol y has degree one. Thus, denoting its only neighbour as v, the

value of v is recovered by setting v = y.

3. Update.

4. If all k input symbols have been recovered, decoding is successful and iterative

decoding ends. Otherwise, go to step 1.

"""

symbols_n = len(symbols)

assert symbols_n > 0, "There are no symbols to decode."

# We keep `blocks_n` notation and create the empty list

blocks_n = blocks_quantity

blocks = [None] * blocks_n

# Recover the degrees and associated neighbors using the seed (the index, cf. encoding).

symbols = recover_graph(symbols, blocks_n)

print("Graph built back. Ready for decoding.", flush=True)

solved_blocks_count = 0

iteration_solved_count = 0

start_time = time.time()

while iteration_solved_count > 0 or solved_blocks_count == 0:

iteration_solved_count = 0

# Search for solvable symbols

for i, symbol in enumerate(symbols):

# Check the current degree. If it's 1 then we can recover data

if symbol.degree == 1:

iteration_solved_count += 1

block_index = next(iter(symbol.neighbors))

symbols.pop(i)

# This symbol is redundant: another already helped decoding the same block

if blocks[block_index] is not None:

continue

blocks[block_index] = symbol.data

if VERBOSE:

print("Solved block_{} with symbol_{}".format(block_index, symbol.index))

# Update the count and log the processing

solved_blocks_count += 1

log("Decoding", solved_blocks_count, blocks_n, start_time)

# Reduce the degrees of other symbols that contains the solved block as neighbor

reduce_neighbors(block_index, blocks, symbols)

print("\n----- Solved Blocks {:2}/{:2} --".format(solved_blocks_count, blocks_n))

return np.asarray(blocks), solved_blocks_count