A slice (3) of a picture (1) is encoded by hierarchically splitting a largest coding unit, LCU, (10) of the picture (1) into multiple smaller coding units, CUs (20, 30, 40). A start of the slice (3) is defined to coincide with the border between a first CU (30, 40B) and a preceding CU (40, 40A) of the LCU (10). Address information is generated that allows identification of the first CU (30, 40B) within the picture (1) by defining the position of the first CU (30, 40B) and the size of the largest possible CU (30) that can occupy this position within the picture (1). The address information is included in a coded representation (50) of the picture (1). The address information enables positioning slice starts also within LCUs (10), which slice starts thereby do not need to be limited between LCU borders.